This is my eighth day of the August Challenge

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

Bubble sort

Simple implementation of bubble sort

Bubble sort is simple swap sort. The core of exchange sort is exchange. The main idea is to select two records in the sequence to be sorted, compare their key codes, and exchange their positions if they are in reverse order.

The basic idea of bubble sort

  1. The whole record sequence to be sorted is divided into ordered region and unordered region. The initial state of the ordered region is empty, and the unordered region includes all the elements to be sorted.

  2. Compare the keys of adjacent records in the disordered region from front to back, and exchange the keys in reverse order. After each cycle, the record with the largest keyword value in the disordered region is entered into the ordered region: after the first cycle, the maximum value bubbles to the right, and after the second cycle, the second largest value bubbles to the second position on the right.

  3. For a sequence of n elements, it takes at most n-1 rounds of bubble sort to get all the elements sorted

Code implementation

//1. Buddle sorting -(void)buddleSort:(NSMutableArray*)arr{for (int I = 0; i<arr.count; i++) { for (int j = 0; j<arr.count-1-i; j++) { if ([arr[j] intValue] > [arr[j+1] intValue]) { NSNumber*tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; }}}}Copy the code

Optimization of bubble sort

Optimization of a

Suppose we bubble sort the sort arr[]={1,2,3,4,5,6,7,8,10,9}. After the first sort, after swapping 10 and 9, all the elements are already ordered, and the next eight sort runs are redundant and nothing is done. So we can put a mark in the place of exchange, and if there is no exchange in that order, it means that the set of data is in order, so we don’t have to go any further.

Apply to data that is sequential but unordered (e.g., 1, 2,3, 4, 7,6,5).

-(void)buddleSortOptimize1:(NSMutableArray*)arr{ for (int i = 0; i<arr.count; i++) { int flag = 0; for (int j = 0; j<arr.count-1-i; j++) { if ([arr[j] intValue] > [arr[j+1] intValue]) { NSNumber*tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp flag = 1; }} if (flag == 0) {// If (flag == 0); }}}Copy the code

Optimization of two

If pos is not swapped in the last round, then pos is ordered, and the next round compares the elements before pos

Optimization idea: record the position of the last exchange of each round of the cycle, the next sort from the first to the end of the last record of the position.

Applies to sequences that are mostly unordered and the smaller part ordered (1,2,5,7,4,3,6,8,9,10)

-(void)buddleSortOptimize2:(NSMutableArray*)arr{ int pos = 0; Int k = (int)arr.count-1; For (int I = 0; i<arr.count; i++) { int flag = 0; for (int j = 0; j<k; j++) { if ([arr[j] intValue] > [arr[j+1] intValue]) { NSNumber*tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; flag = 1; Pos = j; }} if (flag == 0) {// If no element has been exchanged, then return; } k = pos; // update k}}Copy the code