You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: Selection Sort/README.markdown
+17-17Lines changed: 17 additions & 17 deletions
Original file line number
Diff line number
Diff line change
@@ -1,6 +1,6 @@
1
1
# Selection Sort
2
2
3
-
Goal: Sort an array from low to high (or high to low).
3
+
Goal: To sort an array from low to high (or high to low).
4
4
5
5
You are given an array of numbers and need to put them in the right order. The selection sort algorithm divides the array into two parts: the beginning of the array is sorted, while the rest of the array consists of the numbers that still remain to be sorted.
6
6
@@ -10,20 +10,20 @@ This is similar to [insertion sort](../Insertion%20Sort/), but the difference is
10
10
11
11
It works as follows:
12
12
13
-
- Find the lowest number in the array. You start at index 0, loop through all the numbers in the array, and keep track of what the lowest number is.
14
-
- Swap the lowest number you've found with the number at index 0. Now the sorted portion consists of just the number at index 0.
13
+
- Find the lowest number in the array. You must start at index 0, loop through all the numbers in the array, and keep track of what the lowest number is.
14
+
- Swap the lowest number with the number at index 0. Now, the sorted portion consists of just the number at index 0.
15
15
- Go to index 1.
16
16
- Find the lowest number in the rest of the array. This time you start looking from index 1. Again you loop until the end of the array and keep track of the lowest number you come across.
17
-
- Swap it with the number at index 1. Now the sorted portion contains two numbers and extends from index 0 to index 1.
17
+
- Swap the lowest number with the number at index 1. Now, the sorted portion contains two numbers and extends from index 0 to index 1.
18
18
- Go to index 2.
19
-
- Find the lowest number in the rest of the array, starting from index 2, and swap it with the one at index 2. Now the array is sorted from index 0 to 2; this range contains the three lowest numbers in the array.
20
-
- And so on... until no numbers remain to be sorted.
19
+
- Find the lowest number in the rest of the array, starting from index 2, and swap it with the one at index 2. Now, the array is sorted from index 0 to 2; this range contains the three lowest numbers in the array.
20
+
- And continue until no numbers remain to be sorted.
21
21
22
-
It's called a "selection" sort, because at every step you search through the rest of the array to select the next lowest number.
22
+
It nis called a "selection" sort because at every step you search through the rest of the array to select the next lowest number.
23
23
24
24
## An example
25
25
26
-
Let's say the numbers to sort are `[ 5, 8, 3, 4, 6 ]`. We also keep track of where the sorted portion of the array ends, denoted by the `|` symbol.
26
+
Suppose the numbers to sort are `[ 5, 8, 3, 4, 6 ]`. We also keep track of where the sorted portion of the array ends, denoted by the `|` symbol.
27
27
28
28
Initially, the sorted portion is empty:
29
29
@@ -43,7 +43,7 @@ Again, we look for the lowest number, starting from the `|` bar. We find `4` and
43
43
[ 3, 4 | 5, 8, 6 ]
44
44
* *
45
45
46
-
With every step, the `|` bar moves one position to the right. We again look through the rest of the array and find `5` as the lowest number. There's no need to swap `5` with itself and we simply move forward:
46
+
With every step, the `|` bar moves one position to the right. We again look through the rest of the array and find `5` as the lowest number. There is no need to swap `5` with itself, and we simply move forward:
47
47
48
48
[ 3, 4, 5 | 8, 6 ]
49
49
*
@@ -52,7 +52,7 @@ This process repeats until the array is sorted. Note that everything to the left
52
52
53
53
[ 3, 4, 5, 6, 8 |]
54
54
55
-
As you can see, selection sort is an *in-place* sort because everything happens in the same array; no additional memory is necessary. You can also implement this as a *stable* sort so that identical elements do not get swapped around relative to each other (note that the version given below isn't stable).
55
+
The selection sort is an *in-place* sort because everything happens in the same array without using additional memory. You can also implement this as a *stable* sort so that identical elements do not get swapped around relative to each other (note that the version given below is not stable).
56
56
57
57
## The code
58
58
@@ -90,27 +90,27 @@ selectionSort(list)
90
90
91
91
A step-by-step explanation of how the code works:
92
92
93
-
1. If the array is empty or only contains a single element, then there's not much point to sorting it.
93
+
1. If the array is empty or only contains a single element, then there is no need to sort.
94
94
95
-
2. Make a copy of the array. This is necessary because we cannot modify the contents of the `array` parameter directly in Swift. Like Swift's own `sort()`, the `selectionSort()` function will return a sorted *copy* of the original array.
95
+
2. Make a copy of the array. This is necessary because we cannot modify the contents of the `array` parameter directly in Swift. Like the Swift's `sort()` function, the `selectionSort()` function will return a sorted *copy* of the original array.
96
96
97
97
3. There are two loops inside this function. The outer loop looks at each of the elements in the array in turn; this is what moves the `|` bar forward.
98
98
99
99
4. This is the inner loop. It finds the lowest number in the rest of the array.
100
100
101
101
5. Swap the lowest number with the current array index. The `if` check is necessary because you can't `swap()` an element with itself in Swift.
102
102
103
-
In summary: For each element of the array, selection sort swaps positions with the lowest value from the rest of the array. As a result, the array gets sorted from the left to the right. (You can also do it right-to-left, in which case you always look for the largest number in the array. Give that a try!)
103
+
In summary: For each element of the array, the selection sort swaps positions with the lowest value from the rest of the array. As a result, the array gets sorted from the left to the right. (You can also do it right-to-left, in which case you always look for the largest number in the array. Give that a try!)
104
104
105
-
> **Note:** The outer loop ends at index `a.count - 2`. The very last element will automatically always be in the correct position because at that point there are no other smaller elements left.
105
+
> **Note:** The outer loop ends at index `a.count - 2`. The very last element will automatically be in the correct position because at that point there are no other smaller elements left.
106
106
107
-
The source file [SelectionSort.swift](SelectionSort.swift) has a version of this function that uses generics, so you can also use it to sort strings and other types.
107
+
The source file [SelectionSort.swift](SelectionSort.swift) has a version of this function that uses generics, so you can also use it to sort strings and other data types.
108
108
109
109
## Performance
110
110
111
-
Selection sort is easy to understand but it performs quite badly,**O(n^2)**. It's worse than [insertion sort](../Insertion%20Sort/) but better than [bubble sort](../Bubble%20Sort/). The killer is finding the lowest element in the rest of the array. This takes up a lot of time, especially since the inner loop will be performed over and over.
111
+
The selection sort is easy to understand but it performs slow as**O(n^2)**. It is worse than [insertion sort](../Insertion%20Sort/) but better than [bubble sort](../Bubble%20Sort/). Finding the lowest element in the rest of the array is slow, especially since the inner loop will be performed repeatedly .
112
112
113
-
[Heap sort](../Heap%20Sort/) uses the same principle as selection sort but has a really fast method for finding the minimum value in the rest of the array. Its performance is **O(n log n)**.
113
+
The [Heap sort](../Heap%20Sort/) uses the same principle as selection sort but has a fast method for finding the minimum value in the rest of the array. The heap sort' performance is **O(n log n)**.
0 commit comments