quickselect is a selection algorithm to find the kthk-th smallest element in an unordered list.
this is the Pseudo code I was follwingfollowing
In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts: those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element
list[pivotIndex]:function partition(list, left, right, pivotIndex) pivotValue := list[pivotIndex] swap list[pivotIndex] and list[right] // Move pivot to end storeIndex := left for i from left to right-1 if list[i] < pivotValue swap list[storeIndex] and list[i] increment storeIndex swap list[right] and list[storeIndex] // Move pivot to its final place return storeIndexThis is known as the Lomuto partition scheme, which is simpler but less efficient than Hoare's original partition scheme.
In quicksort, we recursively sort both branches, leading to best-case O(n log n) time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:
// Returns the k-th smallest element of list within left..right inclusive // (i.e. left <= k <= right). // The search space within the array is changing for each round - but the list // is still the same size. Thus, k does not need to be updated with each round. function select(list, left, right, k) if left = right // If the list contains only one element, return list[left] // return that element pivotIndex := ... // select a pivotIndex between left and right, // e.g., left + floor(rand() % (right - left + 1)) pivotIndex := partition(list, left, right, pivotIndex) // The pivot is in its final sorted position if k = pivotIndex return list[k] else if k < pivotIndex return select(list, left, pivotIndex - 1, k) else return select(list, pivotIndex + 1, right, k)
quickselect is a selection algorithm to find the kth smallest element in an unordered list.
this is the Pseudo code I was follwing
In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts: those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element
list[pivotIndex]:function partition(list, left, right, pivotIndex) pivotValue := list[pivotIndex] swap list[pivotIndex] and list[right] // Move pivot to end storeIndex := left for i from left to right-1 if list[i] < pivotValue swap list[storeIndex] and list[i] increment storeIndex swap list[right] and list[storeIndex] // Move pivot to its final place return storeIndexThis is known as the Lomuto partition scheme, which is simpler but less efficient than Hoare's original partition scheme.
In quicksort, we recursively sort both branches, leading to best-case O(n log n) time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:
// Returns the k-th smallest element of list within left..right inclusive // (i.e. left <= k <= right). // The search space within the array is changing for each round - but the list // is still the same size. Thus, k does not need to be updated with each round. function select(list, left, right, k) if left = right // If the list contains only one element, return list[left] // return that element pivotIndex := ... // select a pivotIndex between left and right, // e.g., left + floor(rand() % (right - left + 1)) pivotIndex := partition(list, left, right, pivotIndex) // The pivot is in its final sorted position if k = pivotIndex return list[k] else if k < pivotIndex return select(list, left, pivotIndex - 1, k) else return select(list, pivotIndex + 1, right, k)
quickselect is a selection algorithm to find the k-th smallest element in an unordered list.
this is the Pseudo code I was following
In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts: those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element
list[pivotIndex]:function partition(list, left, right, pivotIndex) pivotValue := list[pivotIndex] swap list[pivotIndex] and list[right] // Move pivot to end storeIndex := left for i from left to right-1 if list[i] < pivotValue swap list[storeIndex] and list[i] increment storeIndex swap list[right] and list[storeIndex] // Move pivot to its final place return storeIndexThis is known as the Lomuto partition scheme, which is simpler but less efficient than Hoare's original partition scheme.
In quicksort, we recursively sort both branches, leading to best-case O(n log n) time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:
// Returns the k-th smallest element of list within left..right inclusive // (i.e. left <= k <= right). // The search space within the array is changing for each round - but the list // is still the same size. Thus, k does not need to be updated with each round. function select(list, left, right, k) if left = right // If the list contains only one element, return list[left] // return that element pivotIndex := ... // select a pivotIndex between left and right, // e.g., left + floor(rand() % (right - left + 1)) pivotIndex := partition(list, left, right, pivotIndex) // The pivot is in its final sorted position if k = pivotIndex return list[k] else if k < pivotIndex return select(list, left, pivotIndex - 1, k) else return select(list, pivotIndex + 1, right, k)
quickselect is a selection algorithm to find the kth smallest element in an unordered list.
this is the Pseudo code I was follwing
In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts: those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element
list[pivotIndex]:function partition(list, left, right, pivotIndex) pivotValue := list[pivotIndex] swap list[pivotIndex] and list[right] // Move pivot to end storeIndex := left for i from left to right-1 if list[i] < pivotValue swap list[storeIndex] and list[i] increment storeIndex swap list[right] and list[storeIndex] // Move pivot to its final place return storeIndexThis is known as the Lomuto partition scheme, which is simpler but less efficient than Hoare's original partition scheme.
In quicksort, we recursively sort both branches, leading to best-case O(n log n) time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:
// Returns the k-th smallest element of list within left..right inclusive // (i.e. left <= k <= right). // The search space within the array is changing for each round - but the list // is still the same size. Thus, k does not need to be updated with each round. function select(list, left, right, k) if left = right // If the list contains only one element, return list[left] // return that element pivotIndex := ... // select a pivotIndex between left and right, // e.g., left + floor(rand() % (right - left + 1)) pivotIndex := partition(list, left, right, pivotIndex) // The pivot is in its final sorted position if k = pivotIndex return list[k] else if k < pivotIndex return select(list, left, pivotIndex - 1, k) else return select(list, pivotIndex + 1, right, k)
quickselect is a selection algorithm to find the kth smallest element in an unordered list.
this is the Pseudo code I was follwing
In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts: those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element
list[pivotIndex]:function partition(list, left, right, pivotIndex) pivotValue := list[pivotIndex] swap list[pivotIndex] and list[right] // Move pivot to end storeIndex := left for i from left to right-1 if list[i] < pivotValue swap list[storeIndex] and list[i] increment storeIndex swap list[right] and list[storeIndex] // Move pivot to its final place return storeIndexThis is known as the Lomuto partition scheme, which is simpler but less efficient than Hoare's original partition scheme.
In quicksort, we recursively sort both branches, leading to best-case O(n log n) time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect:
// Returns the k-th smallest element of list within left..right inclusive // (i.e. left <= k <= right). // The search space within the array is changing for each round - but the list // is still the same size. Thus, k does not need to be updated with each round. function select(list, left, right, k) if left = right // If the list contains only one element, return list[left] // return that element pivotIndex := ... // select a pivotIndex between left and right, // e.g., left + floor(rand() % (right - left + 1)) pivotIndex := partition(list, left, right, pivotIndex) // The pivot is in its final sorted position if k = pivotIndex return list[k] else if k < pivotIndex return select(list, left, pivotIndex - 1, k) else return select(list, pivotIndex + 1, right, k)
Quick Select C#
I tried to implement https://en.wikipedia.org/wiki/Quickselect
Please review the coding style and clarity
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace ArrayQuestions
{
[TestClass]
public class QuickSelect
{
[TestMethod]
public void QuickSelectAlgoTest()
{
int[] arr = {9, 8, 7, 6, 5, 0, 1, 2, 3, 4};
int[] res = Select(arr, 6);
for (int i = 0; i < 6; i++)
{
Assert.IsTrue(res[i] <= 6, $"The res[i] {res[i]} was not greater than six");
}
}
//Partially sort array such way that elements before index position n are smaller or equal than element at position n
//And elements after n are larger or equal.
public int[] Select(int[] input,int n)
{
//keep original array
int[] partiallySortedArray = (int[])input.Clone();
int startIndex = 0;
var endIndex = input.Length - 1;
var pivotIndex = n;
Random r = new Random();
while (endIndex > startIndex)
{
pivotIndex = QuickSelectPartition(partiallySortedArray, startIndex, endIndex, pivotIndex);
if (pivotIndex == n)
{
break;
}
if (pivotIndex > n)
{
endIndex = pivotIndex - 1;
}
else
{
startIndex = pivotIndex + 1;
}
pivotIndex = r.Next(startIndex, endIndex);
}
return partiallySortedArray;
}
private int QuickSelectPartition(int[] array, int startIndex, int endIndex, int pivotIndex)
{
int pivotValue = array[pivotIndex];
Swap(ref array[pivotIndex], ref array[endIndex]);
for (int i = startIndex; i < endIndex; i++)
{
if (array[i].CompareTo(pivotValue) > 0)
{
continue;
}
Swap(ref array[i], ref array[startIndex]);
startIndex++;
}
Swap(ref array[endIndex], ref array[startIndex]);
return startIndex;
}
private void Swap(ref int i, ref int i1)
{
int temp = i;
i = i1;
i1 = temp;
}
}
}