Sorting with closure mechanism

iOS Programming (7th Edition) 2. The Swift Language
#1

Hello,
this is basic language question about closure sorting of array:

let compareAscending = { (i: Int, j: Int) -> Bool in
return i < j
}

var numbers = [42, 9, 12, -17]
numbers.sort(by: compareAscending)

I don’t get how the underlying sorting mechanism works.
I get it compares two numbers and returns a bool if first number > second number, but how does it sort the entire array then?
What is the sequence of operations?

#2

The sorting algorithm is provided by the array type & is built into Swift. It’s a variation on QuickSort called IntroSort.

1 Like
#3

If you are new to the topic of sorting, here is a simple example.

// To sort the array of numbers: [19, 17, 02, 05, 03]

Let _(x) := find the smallest number less than the one at index 'x' and swap them. To find the smallest number, use the predicate compareAscending.

Repeat _(x) for indexes: 0, 1, 2, 3, 4

_ (0): 19, 17, 02, 05, 03      // result of _(x) on the next line

_ (1): 02, 17, 19, 05, 03

_ (2): 02, 03, 19, 05, 17

_ (3): 02, 03, 05, 19, 17

_ (4): 02, 03, 05, 17, 19


// To judge the quality of a sorting algorithm, ask:

- How many steps does it take?

- How much space does it use?
1 Like
#4

Thanks for answer.
I understand it better, now: are as many iterations on the array as there are items in it.

#5

It depends on the sorting algorithm used. Simple sorts, such as the bubble sort shown in ibex10’s post, do work like that. Most sorting implementations use more advanced algorithms that don’t actually iterate over the array over & over, but rather use a divide & conquer method that is significantly faster when sorting a large number of items.

1 Like