Learn sorting algorithms in Objective-C

When I was learning data structures and algorithms, I tried to present the sorting algorithm in the form of animation to make it easier to understand and remember. This article is better to read with [Demo Learning Data Structures and Algorithms in Object-C - Sorting Algorithm](https://github.com/MisterBooo/Play-With-Sort-OC).

Table of contents

* Selection sort

* Bubble sort

* Insertion sort

* Quick sort

* Two-way quick sort

* Three-way quick sort

* Heap sort

* Summary and harvest

* References and Reading

Selection Sort

Selection sort is a simple and intuitive sorting algorithm. No matter what data is entered, the time complexity is O(n?). So when using it, the smaller the data size, the better. The only advantage may be that it does not take up extra memory space.

1. Algorithm steps

1. First find the smallest (largest) element in the unsorted sequence and store it at the beginning of the sorted sequence

2. Continue to look for the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.

3. Repeat step 2 until all elements are sorted.

2. Code Implementation

 #pragma mark - /**Select sort*/  
 - ( void )mb_selectionSort{
 for ( int i = 0; i < self.count; i++) {
 for ( int j = i + 1; j < self.count ; j++) {
 if (self.comparator(self[i],self[j]) == NSOrderedDescending) {
                [self mb_exchangeWithIndexA:i indexB:j];
 }
 }
 }
 }

Bubble Sort

Bubble Sort is also a simple and intuitive sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need to swap, that is, the sequence has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the sequence through swapping.

1. Algorithm steps

1. Compare adjacent elements. If the first is larger than the second, swap them.

2. Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After this step, the last element will be the last number.

3. Repeat the above steps for all elements except the last one.

4. Keep repeating the above steps for fewer and fewer elements each time, until there are no pairs of numbers that need to be compared.

2. Code Implementation

 #pragma mark - /**Bubble sort*/  
 - ( void )mb_bubbleSort{
 bool swapped;
 do {
 swapped = false ;
 for ( int i = 1; i < self.count; i++) {
 if (self.comparator(self[i - 1],self[i]) == NSOrderedDescending) {
                swapped = true ;
                [self mb_exchangeWithIndexA:i indexB:i- 1];
 }
 }
 } while (swapped);
 }

Insertion Sort

Although the code implementation of insertion sort is not as simple and crude as bubble sort and selection sort, its principle should be the easiest to understand, because anyone who has played poker should be able to understand it in seconds. Insertion sort is the simplest and most intuitive sorting algorithm. Its working principle is to build an ordered sequence. For unsorted data, it scans from the back to the front in the sorted sequence, finds the corresponding position and inserts it.

1. Algorithm steps

1. Treat the first element of the sequence to be sorted as an ordered sequence, and the second element to the first element as an unsorted sequence.

2. Scan the unsorted sequence from beginning to end, and insert each scanned element into the appropriate position of the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)

2. Code Implementation

 #pragma mark - /**Insert sort*/  
 - ( void )mb_insertionSort{
 for ( int i = 0; i < self.count; i++) {
 id e = self[i];
 int j;
 for (j = i; j > 0 && self.comparator(self[j - 1],e) == NSOrderedDescending; j--) {
            [self mb_exchangeWithIndexA:j indexB:j- 1];
 }
 self[j] = e;
 }
 }

Merge Sort

Merge sort is an effective sorting algorithm based on the merge operation. This algorithm is a very typical application of the Divide and Conquer method.

As a typical algorithm application of the divide and conquer idea, merge sort is implemented in two ways:

>1. Top-down recursion (all recursive methods can be rewritten using iteration, so there is the second method)

>2. Bottom-up iteration;

This article uses **top-down** merge sort

1. Algorithm steps

1. Apply for space whose size is equal to the sum of the two sorted sequences. This space is used to store the merged sequence.

2. Set two pointers, whose initial positions are the starting positions of the two sorted sequences;

3. Compare the elements pointed to by the two pointers, select the relatively small element to put into the merge space, and move the pointer to the next position;

4. Repeat step 3 until a pointer reaches the end of the sequence;

5. Copy all remaining elements of the other sequence directly to the end of the merged sequence.

2. Code Implementation

 #pragma mark - /**Merge sort from top to bottom*/  
 - ( void )mb_mergeSort{
    [self mb_mergeSortArray:self LeftIndex:0 rightIndex:( int )self.count - 1];
 }
 - ( void )mb_mergeSortArray:(NSMutableArray *)array LeftIndex:( int )l rightIndex: (int )r{
 if (l >= r) return ;
 int mid = (l + r) / 2;
    [self mb_mergeSortArray:self LeftIndex:l rightIndex:mid];
    [self mb_mergeSortArray:self LeftIndex:mid + 1 rightIndex:r];
    [self mb_mergeSortArray:self LeftIndex:l midIndex:mid rightIndex:r];
 }
 - ( void )mb_mergeSortArray:(NSMutableArray *)array LeftIndex:( int )l midIndex:( int )mid rightIndex:( int )r{
    SEL func = NSSelectorFromString(@ "resetSortArray:" );
 // Open up new space r-l+1 space  
    NSMutableArray *aux = [NSMutableArray arrayWithCapacity:r-l+1];
 for ( int i = l; i r){ // If all elements in the right half have been processed  
            self.comparator(nil, nil);
            self[k] = aux[i - l];
 i++;
 } else   if (self.comparator(aux[i - l], aux[j - l]) == NSOrderedAscending){ // The element pointed to by the left half < the element pointed to by the right half  
            self[k] = aux[i - l];
 i++;
 } else {
            self.comparator(nil, nil);
            self[k] = aux[j - l];
 j++;
 } 
          
        NSMutableArray *mutArray = [NSMutableArray array];
        [self enumerateObjectsUsingBlock:^(MBBarView * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            [mutArray addObject:[NSString stringWithFormat:@ "%f" ,obj.frame.size.height]];
 }]; 
          
        objc_msgSendSortArray(self.vc,func,mutArray);
 }
 }

Quick Sort

Quicksort is a sorting algorithm developed by Tony Hall. On average, sorting n items requires Ο(nlogn) comparisons. In the worst case, it requires Ο(n2) comparisons, but this is uncommon. In fact, quicksort is often significantly faster than other Ο(nlogn) algorithms because its inner loop can be implemented efficiently on most architectures.

Quick sort uses a divide and conquer strategy to divide a list into two sub-lists.

Quick sort is another typical application of the divide and conquer idea in sorting algorithms. In essence, quick sort should be regarded as a recursive divide and conquer method based on bubble sort.

The name of quick sort is simple and crude, because as soon as you hear this name, you know its purpose, which is fast and efficient! It is one of the fastest sorting algorithms for processing large data.

1. Algorithm steps

1. Pick an element from the sequence, called the "pivot";

2. Reorder the sequence, placing all elements smaller than the base value in front of the base value, and all elements larger than the base value in the back of the base value (the same number can be on either side). After this partition is exited, the base value is in the middle of the sequence. This is called a partition operation;

3. Recursively sort the subsequences of elements less than the base value and the subsequences of elements greater than the base value;

The optimization of quick sort can be considered to use insertion sort when the partition interval is small.

2. Code Implementation

 #pragma mark - /**Quick sort*/  
 - ( void )mb_quickSort{
 // Pay special attention to the border situation  
    [self mb_quickSort:self indexL:0 indexR: (int )self.count - 1];
 }
 - ( void )mb_quickSort:(NSMutableArray *)array indexL: (int )l indexR: (int )r{
 if (l >= r) return ;
 int p = [self __partition:array indexL:l indexR:r];
    [self mb_quickSort:array indexL:l indexR:p-1];
    [self mb_quickSort:array indexL:p + 1 indexR:r];
 }
 /**
 Perform partition operation on arr[l...r]
 Return p, such that arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
   
 @param array array
 @param l left
 @param r right
 @return Return p
 */  
 - ( int )__partition:(NSMutableArray *)array indexL: (int )l indexR: (int )r{
 int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v  
 for ( int i = l + 1; i <= r ; i++) {
 if ( self.comparator(array[i], array[ l]) == NSOrderedAscending) {
 j++;
 //exchange  
            [self mb_exchangeWithIndexA:j indexB:i];
 }
 }
    self.comparator(nil, nil);
    [self mb_exchangeWithIndexA:j indexB:l];
 return j;
 }

Multi-way quick sort

Too many duplicate keys reduce Quick Sort to O(n^2)

After using double quick sort, our quick sort algorithm can easily handle arrays containing a large number of elements.

The optimization of quick sort can be considered to use insertion sort when the partition interval is small.

1. Algorithm diagram

2. Code Implementation

 #pragma mark - /**Dual-way fast sort*/  
 ///After using double quick sort, our quick sort algorithm can easily handle arrays containing a large number of elements  
 - ( void )mb_identicalQuickSort{
 // Pay special attention to the border situation  
    [self mb_quickSort:self indexL:0 indexR: (int )self.count - 1];
 }
 - ( void )mb_identicalQuickSort:(NSMutableArray *)array indexL: (int )l indexR: (int )r{
 if (l >= r) return ;
 int p = [self __partition2:array indexL:l indexR:r];
    [self mb_quickSort:array indexL:l indexR:p-1];
    [self mb_quickSort:array indexL:p + 1 indexR:r];
 }
 - ( int )__partition2:(NSMutableArray *)array indexL: (int )l indexR: (int )r{
 // Randomly select a value in the range of arr[l...r] as the pivot point  
    [self mb_exchangeWithIndexA:l indexB:(arc4random()%(r-l+1))];
 id v = array[l];
 // arr[l+1...i) = v  
 int i = l + 1, j = r;
 while ( true ) { 
          
 while (i l + 1 && self.comparator(array[j],v) == NSOrderedDescending)
 j--; 
          
 if (i > j) {
 break ;
 }
        [self mb_exchangeWithIndexA:i indexB:j]; 
          
 i++;
 j--;
 }
    [self mb_exchangeWithIndexA:l indexB:j];
 return j;
 }

Three-way quick sort

For arrays containing a large amount of repeated data, three-way quick sort has a huge advantage

For general random arrays and nearly ordered arrays, the efficiency of three-way quick sort is not perfect, but it is within a very acceptable range.

Therefore, in some languages, three-way quick sort is the default sorting algorithm used in language library functions. For example, Java:)

The optimization of quick sort can be considered to use insertion sort when the partition interval is small.

1. Algorithm diagram

2. Code Implementation

 #pragma mark - /**Three-way fast sort*/  
 // For arrays containing a large amount of repeated data, three-way quick sorting has a huge advantage  
 - ( void )mb_quick3WaysSort{
 // Pay special attention to the border situation  
    [self mb_quick3WaysSort:self indexL:0 indexR: (int )self.count - 1];
 }
 /// Recursive three-way quick sort algorithm  
 - ( void )mb_quick3WaysSort:(NSMutableArray *)array indexL:( int )l indexR:( int )r{
 if (l >= r) return ; 
      
    self.comparator(nil, nil);
 // Randomly select a value in the range of arr[l...r] as the pivot point  
    [self mb_exchangeWithIndexA:l indexB:(arc4random_uniform(r-l+1) + l)]; 
      
 id v = array[l]; 
      
 int lt = l; // array[l+1...lt] < v  
 int gt = r + 1; // array[gt...r] > v  
 int i = l + 1; // array[lt+1...i) == v   
      
 while (i < gt) {
 if ([self compareWithBarOne:array[i] andBarTwo:v] == NSOrderedAscending) {
            self.comparator(nil, nil);
            [self mb_exchangeWithIndexA:i indexB:lt + 1];
 i++;
 lt++;
 } else   if ([self compareWithBarOne:array[i] andBarTwo:v] == NSOrderedDescending){
            self.comparator(nil, nil);
            [self mb_exchangeWithIndexA:i indexB:gt - 1];
 gt--;
        } else { //array[i] == v  
 i++;
 }
 }
 self.comparator(nil,nil);
    [self mb_exchangeWithIndexA:l indexB:lt];
    [self mb_quick3WaysSort:array indexL:l indexR:lt-1];
    [self mb_quick3WaysSort:array indexL:gt indexR:r]; 
      
 }

Stacking order

Heapsort refers to a sorting algorithm designed using the heap data structure. A heap is a structure that approximates a complete binary tree and satisfies the properties of a heap: the key value or index of a child node is always smaller than (or larger than) its parent node. Heapsort can be said to be a selection sort that uses the concept of a heap to sort. There are two methods:

Max-top heap: The value of each node is greater than or equal to the value of its child node, and is used for ascending order in the heap sort algorithm;

Mini-top heap: The value of each node is less than or equal to the value of its child node, which is used for descending order in the heap sort algorithm;

The average time complexity of heap sort is O(nlogn).

1. Algorithm steps

1. Create a heap H[0...n-1];

2. Swap the head of the heap (the highest value) and the tail of the heap;

3. Reduce the size of the heap by 1 and call shift_down(1) to adjust the top data of the new array to the corresponding position;

4. Repeat step 2 until the heap size is 1

2. Code Implementation

 ///shift_down operation  
 - ( void )shiftDown:( int )k{
 while (2 * k <= _count) {
 int j = 2 * k;
 if (j + 1 <= _count && [self heapCompareWithBarOne:_data[j + 1] andBarTwo:_data[j]] == NSOrderedDescending) j++; //The left child is smaller than the right child  
 if ([self heapCompareWithBarOne:_data[k] andBarTwo:_data[j]] == NSOrderedDescending) break ; //The parent node is greater than the child node  
        self.comparator(nil, nil);
        [_data mb_exchangeWithIndexA:k indexB:j];
 k = j;
 }
 }

Ending and Harvest

Summarize:

In the process of relearning data structures and algorithms, I fully realized the importance of learning these so-called **basic knowledge**, and understood that in order to further improve the level of iOS development, the basic links cannot be ignored. It also happened that in this study, the deep traversal of the graph was used to solve the problem of finding the backtracking source in the process of studying the buried points.

Gains:

> 1. Basic sorting whiteboard programming

> 2. Add categories to runtime

> 3. runtime's objc_msgSend()

> 4. Deep copy and shallow copy

> 5. Use of GCD semaphores

If you have gained something from reading this, please give it a star on [Github](https://github.com/MisterBooo/Play-With-Sort-OC)**

References and Reading

* [A GitBook online book about sorting algorithms, "Top Ten Classic Sorting Algorithms", implemented in JavaScript & Python & Go](https://github.com/hustcc/JS-Sorting-Algorithm)

* [Learn Data Structure and Algorithm in JavaScript](https://juejin.im/post/594dfe795188250d725a220a)

* [Sorting animation](https://github.com/JiongXing/JXSort)