Swift implementation of the quick sort algorithm code example

  • 2020-05-17 06:38:44
  • OfStack

thought

Quicksort as a divide-and-conquer representative, usually implemented by three steps

1. Select one element from the data as the "benchmark" (pivot), and usually select the last element;
2. All elements in the partition (partition) that are smaller than "reference" are moved to the left of "reference"; All elements larger than "reference" are moved to the right of "reference". At the end of the partitioning operation, the position of the reference element is its final sorted position.
3. Repeat steps 1 and 2 for the left and right subsets of the benchmark until there is only one element left in all subsets.

Implementation:


func quickSort(inout a: [Int], l: Int, r: Int) {

 if l < r {
 var i = l,
  j = r,
  x = a[i]
 while i < j && a[j] >= x {
  j -= 1
 }
 if i < j {
  a[i] = a[j]
  i += 1
 }
 while i < j && a[i] < x {
  i += 1
 }
 if i < j {
  a[j] = a[i]
  j -= 1
 }

 a[i] = x

 quickSort( & a, l: l, r: i - 1)
 quickSort( & a, l: i + 1, r: r)
 }


}

var b = [8, 7, 6, 5, 4, 3, 2, 1]

quickSort( & b, l: 0, r: 7)

print(b) 


Related articles: