Rosetta Code

Sorting algorithms/Quicksort: Difference between revisions

← Older editNewer edit →
Content deleted Content added
CNHume (talk | contribs)
159 edits
CNHume (talk | contribs)
159 edits
Added an assertion which holds after each call to partition()
Line 1,124:
 
//
//[Assert]left partition()< updatesright and entries[first:right] and<= the indexes until rightmedian <= entries[left:last]
// and the following invariants hold:
//▼
// entries[first:right] < median < entries[left:last]
// entries[right + 1:left - 1] == median
//
var leftLength = right + 1 - first;
Line 1,146 ⟶ 1,142:
last = right;
length = leftLength;
▲ //}
}▼
}▼
 
private static void partition(T[] entries, T pivot, ref Int32 left, ref Int32 right) {▼
while (left <= right) {▼
while (pivot.CompareTo(entries[left]) > 0) left++;▼
while (pivot.CompareTo(entries[right]) < 0) right--;▼
 
if (left < right) // Move entries to their correct partition▼
Swap(entries, left++, right--);▼
else if (left == right) { // NoSwap swap neededunnecessary▼
left++;▼
right--;▼
}
}
Line 1,164 ⟶ 1,174:
InsertionSort<T>.Sort(entries, first, right);
return entries[first + sampleSize / 2];
▲ }
 
▲ private static void partition(T[] entries, T pivot, ref Int32 left, ref Int32 right) {
▲ while (left <= right) {
▲ while (pivot.CompareTo(entries[left]) > 0)
left++; // pivot follows entry
▲ while (pivot.CompareTo(entries[right]) < 0)
right--; // pivot precedes entry
 
▲ if (left < right) // Move entries to their correct partition
▲ Swap(entries, left++, right--);
▲ else if (left == right) { // No swap needed
▲ left++;
▲ right--;
}
▲ }
}
 
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"