Shulou(Shulou.com)06/02 Report--

In this issue, the editor will bring you about the Objective-C implementation of the major sorting algorithms and how the graphical demonstration is compared. The article is rich in content and analyzes and describes for you from a professional point of view. I hope you can get something after reading this article.

Several basic sorting algorithms are realized with Objective-C, and the sorting process is graphically displayed. In fact, the algorithm is still very interesting.

Select sort

Bubbling sort

Insert sort

Quick sort

Select sort

Take ascending order as an example.

The choice of sorting is easier to understand, and the summary of a sentence is to select the elements that are suitable for this location in turn to fill them.

Tentatively, * elements are the smallest elements. Traverse them back and compare them with the smallest elements one by one. If smaller elements are found, they will swap places with the previous "minimum elements". Achieve the goal of updating the smallest element.

After a traversal is completed, you can ensure that the smallest elements have been placed in front of the traversal that has just been completed. Then narrow the sort range, and the new sort starts with the second element of the array.

Repeat steps 1 and 2 in the new round of sorting until the scope cannot be narrowed down.

Select sort

The following methods are implemented in NSMutableArray+JXSort.m

-(void) jx_selectionSortUsingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback {if (self.count = = 0) {return;} for (NSInteger I = 0; I

< self.count - 1; i ++) { for (NSInteger j = i + 1; j < self.count; j ++) { if (comparator(self[i], self[j]) == NSOrderedDescending) { [self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback]; } } } } 冒泡排序 在一趟遍历中，不断地对相邻的两个元素进行排序，小的在前大的在后，这样会造成大值不断沉底的效果，当一趟遍历完成时，***的元素会被排在后方正确的位置上。 然后缩小排序范围，即去掉***方位置正确的元素，对前方数组进行新一轮遍历，重复第1步骤。直到范围不能缩小为止，排序完成。 冒泡排序- (void)jx_bubbleSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { if (self.count == 0) { return; } for (NSInteger i = self.count - 1; i >

0; I--) {for (NSInteger j = 0; j)

< i; j ++) { if (comparator(self[j], self[j + 1]) == NSOrderedDescending) { [self jx_exchangeWithIndexA:j indexB:j + 1 didExchange:exchangeCallback]; } } } } 插入排序 插入排序是从一个乱序的数组中依次取值，插入到一个已经排好序的数组中。 这看起来好像要两个数组才能完成，但如果只想在同一个数组内排序，也是可以的。此时需要想象出两个区域：前方有序区和后方乱序区。 1、分区。开始时前方有序区只有一个元素，就是数组的***个元素。然后把从第二个元素开始直到结尾的数组作为乱序区。 2、从乱序区取***个元素，把它正确插入到前方有序区中。把它与前方无序区的***一个元素比较，亦即与它的前一个元素比较。 如果比前一个元素要大，则不需要交换，这时有序区扩充一格，乱序区往后缩减一格，相当于直接拼在有序区末尾。 如果和前一个元素相等，则继续和前二元素比较、再和前三元素比较……如果往前遍历到头了，发现前方所有元素值都长一个样的话(囧)，那也可以，不需要交换，这时有序区扩充一格，乱序区往后缩减一格，相当于直接拼在有序区末尾。如果比前一个元素大呢?对不起作为有序区不可能出现这种情况。如果比前一个元素小呢，请看下一点。 如果比前一个元素小，则交换它们的位置。交换完后，继续比较取出元素和它此时的前一个元素，若更小就交换，若相等就比较前一个，直到遍历完成。至此，把乱序区***个元素正确插入到前方有序区中。 3、往后缩小乱序区范围，继续取缩小范围后的***个元素，重复第2步骤。直到范围不能缩小为止，排序完成。 插入排序- (void)jx_insertionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback { if (self.count == 0) { return; } for (NSInteger i = 1; i < self.count; i ++) { for (NSInteger j = i; j >

0 & & comparator (self [j], self [j-1]) = = NSOrderedAscending; j -) {[self jx_exchangeWithIndexA:j indexB:j-1 didExchange:exchangeCallback];}

Quick sort

There are several versions of express arrangement, which can be roughly divided into:

The original platoon.

To create a quick arrangement that disrupts the array order in advance in order to be suitable for an efficient sorting environment.

A three-way syncopated fast arrangement optimized for a large number of repeated values in an array.

Only the original fast platoon is discussed here.

I see two different ways of thinking about when and who to exchange during the fast scheduling process:

When both the left and right cursors stop, swap the elements that the two cursors point to. The position of the pivot remains the same for the time being, and the pivot position is not updated until the two cursors meet and coincide, and the pivot and the elements referred to by the cursor are exchanged.

When the right cursor finds an element smaller than the pivot, it immediately changes the pivot to the position of the cursor, while the element of the cursor position is moved to the pivot. Complete a pivot update. Then the left cursor looks for elements larger than the pivot, in the same way.

The first idea can effectively reduce the switching frequency and position the pivot after the cursor encounter, which will lead to a slight increase in the number of comparisons.

The second train of thought exchange operation will be more frequent, but in the process of exchange, the position of the pivot will also be constantly updated, when the cursor meets, the positioning of the pivot is also completed.

After trying to implement both ideas, I still like the second, even though there are more swapping operations, but essentially swapping is just an assignment to a specific location of the array, which is pretty fast.

Select a value from the array to be sorted as the reference line for the partition, and you can generally select * elements. This selected value can be called pivot pivot, and it will be moved over and over again in a sort, only to the correct position in the entire array.

The goal of a sort is to put elements smaller than the pivot in the front, elements larger than the pivot in the rear, and pivot in the middle. It seems that what a sort essentially does is partition the array. Next consider how to complete a partition.

Remember a cursor I, pointing to the first bit of the array to be sorted, which will continue to move backwards

Remember another cursor j, pointing to the last bit of the array to be sorted, and it will keep moving forward.

It can be foreseen that when I and j finally meet, when they meet, it is when the sequence is completed.

Now let the cursor j scan from back to front, looking for the element x smaller than the pivot, find it and stop, ready to throw it to the front.

Sorting in the same array does not expand the capacity of the array, so how to throw it away?

Because the first element has just been selected as pivot, their current positional relationship is pivot. X .

And the sorting target is ascending order, x is a small value but placed after the pivot, inappropriate, need to exchange their positions.

After the exchange, their positional relationship becomes x. Pivot . At this point j points to pivot,i and points to x.

Now let the cursor I scan backwards, looking for the element y larger than the pivot, find it, stop, and swap with pivot.

The position relationship after completion is pivot. Y, where I points to pivot, that is, pivot moves to the location of I.

Here is a small optimization. At the beginning of the I backward scan, I points to x, but in the last round of j cursor scanning, we already knew that x is smaller than pivot, so we can let I skip x without having to compare x with pivot again.

The conclusion is that after the exchange of the j cursor, move I back one bit by the way, I +.

Similarly, after the exchange of the I cursor is completed, move j forward one bit, j -.

What if an element equal to the pivot is found during the scan?

Since we do not discuss the fast scheduling optimization algorithm of three-dimensional segmentation, the answer here is: ignore it.

As they are sorted one at a time, they are slowly pushed back by smaller elements and pushed forward by larger elements, and the result is that they all move to the middle with the pivot.

When I and j meet, both I and j point to pivot. In our partition method, I is returned, that is, the pivot position is returned after the partition is complete.

Next, let the two separate arrays partition according to the above steps, which is a recursive process until the sorting is complete when the array can no longer be divided.

Quick sorting is a very talented design, the implementation is not complicated, the key is that it is really fast.

Quick sort. Gif

-(void) jx_quickSortUsingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback {

If (self.count = = 0) {

Return

}

[self jx_quickSortWithLowIndex:0 highIndex:self.count-1 usingComparator:comparator didExchange:exchangeCallback]

}

-(void) jx_quickSortWithLowIndex: (NSInteger) low highIndex: (NSInteger) high usingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback {

If (low > = high) {

Return

}

NSInteger pivotIndex = [self jx_quickPartitionWithLowIndex:low highIndex:high usingComparator:comparator didExchange:exchangeCallback]

[self jx_quickSortWithLowIndex:low highIndex:pivotIndex-1 usingComparator:comparator didExchange:exchangeCallback]

[self jx_quickSortWithLowIndex:pivotIndex + 1 highIndex:high usingComparator:comparator didExchange:exchangeCallback]

}

-(NSInteger) jx_quickPartitionWithLowIndex: (NSInteger) low highIndex: (NSInteger) high usingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback {

Id pivot = self [low]

NSInteger I = low

NSInteger j = high

While (I < j) {

/ / skip elements greater than or equal to pivot

While (I < j & & comparator (self [j], pivot)! = NSOrderedAscending) {

J--

}

If (I < j) {

/ / I and j did not meet, indicating that an element smaller than pivot was found. exchange.

[self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback]

I + +

}

/ / skip elements less than or equal to pivot

While (I < j & & comparator (self [I], pivot)! = NSOrderedDescending) {

I + +

}

If (I < j) {

/ / I and j did not meet, indicating that an element greater than pivot was found. exchange.

[self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback]

J--

}

}

Return i

}

UI implementation

Now let's talk about the implementation of UI.

NSMutableArray+JXSort.h

As you can see from the previous sorting code, I wrote a classification for NSMutableArray, and the sorting logic is written in the classification, which has nothing to do with the view.

Typedef NSComparisonResult (^ JXSortComparator) (id obj1, id obj2); typedef void (^ JXSortExchangeCallback) (id obj1, id obj2); @ interface NSMutableArray (JXSort) / / Select sort-(void) jx_selectionSortUsingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback; / / Bubble sort-(void) jx_bubbleSortUsingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback; / / insert sort-(void) jx_insertionSortUsingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback / / Quick sort-(void) jx_quickSortUsingComparator: (JXSortComparator) comparator didExchange: (JXSortExchangeCallback) exchangeCallback; @ end

External callers only need to pass in two parameters:

Comparator code block. This is designed in the style of Apple's original API. When you need to compare the two elements in the array, the sorting method will call the code block and send back the two elements to be compared to the external caller, who will implement the comparison logic and return the comparison results to the sorting method.

ExchangeCallback code block. This parameter is the key to implementing view changes. The sorting method calls this code block each time the exchange of two elements is completed. External callers, such as ViewController, can know the timing of each change in the position of the sorting element, thus synchronizing the changes in the view.

-(void) jx_exchangeWithIndexA: (NSInteger) indexA indexB: (NSInteger) indexB didExchange: (JXSortExchangeCallback) exchangeCallback {id temp = self [indexA]; self [indexA] = self [indexB]; self [indexB] = temp; if (exchangeCallback) {exchangeCallback (temp, self [indexA]);} ViewController.m

The view controller holds an array to be sorted, which is 100 slender rectangles of random length.

@ property (nonatomic, strong) NSMutableArray * barArray

Because we have enhanced NSMutableArray, it can now support a variety of specified types of sorting, and it can also feedback the sorting process to us. When you need to sort barArray, you only need to call:

-(void) quickSort {[self.barArray jx_quickSortUsingComparator: ^ NSComparisonResult (id obj1, id obj2) {return [self compareWithBarOne:obj1 andBarTwo:obj2];} didExchange: ^ (id obj1, id obj2) {[self exchangePositionWithBarOne:obj1 andBarTwo:obj2];}];}

With each callback of didExchange, ViewController swaps the positions of the two views. In this way, the visual effect of continuous sorting is formed.

Control sorting speed

In order to make the sorting process visible to the naked eye, we need to slow down the sorting process.

My approach here is to extend the time it takes to compare two elements to about 0.002 seconds. The result is clear that the less comparison operations an algorithm needs to do, the faster it will be sorted (based on the comparison of the four graphs above, there is no doubt that the fast row has the least comparison operations).

So how do you simulate the time-consuming of the comparison operation?

My approach here is to communicate between the two threads with the help of semaphores.

1. Let the sorting take place in the child thread, blocking the thread when a comparison operation is needed, waiting for the signal to arrive. The idea here is to get a signal in order to make a comparison.

-(NSComparisonResult) compareWithBarOne: (UIView *) barOne andBarTwo: (UIView *) barTwo {/ / simulate the time-consuming dispatch_semaphore_wait (self.sema, DISPATCH_TIME_FOREVER); CGFloat height1 = CGRectGetHeight (barOne.frame); CGFloat height2 = CGRectGetHeight (barTwo.frame); if (height1 = = height2) {return NSOrderedSame;} return height1 < height2? NSOrderedAscending: NSOrderedDescending;}

two。 The main thread enables the timer, which sends a signal every 0.002 seconds to wake up the sorting thread.

Self.sema = dispatch_semaphore_create (0); NSTimeInterval nowTime = [[NSDate date] timeIntervalSince1970]; / / timer signal _ _ weak typeof (self) weakSelf = self; self.timer = [NSTimer scheduledTimerWithTimeInterval:0.002 repeats:YES block: ^ (NSTimer * _ Nonnull timer) {/ / issue semaphore to wake up sorting thread dispatch_semaphore_signal (weakSelf.sema); / / update timing NSTimeInterval interval = [NSDate date] timeIntervalSince1970]-nowTime WeakSelf.timeLabel.text = [NSString stringWithFormat:@ "time (seconds):% 2.3f", interval];}]. This is what the Objective-C implementation and graphical demonstration of the major sorting algorithms shared by Xiaobian are like. If you happen to have similar doubts, please refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.