8000 Revisions in README.markdown · matsoftware/swift-algorithm-club@0f4baf5 · GitHub
[go: up one dir, main page]

Skip to content

Commit 0f4baf5

Browse files
author
Parva9eh
authored
Revisions in README.markdown
I have revised your document to be more concise.
1 parent 36f374e commit 0f4baf5

File tree

1 file changed

+17
-17
lines changed

1 file changed

+17
-17
lines changed

Selection Sort/README.markdown

Lines changed: 17 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
# Selection Sort
22

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).
44

55
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.
66

@@ -10,20 +10,20 @@ This is similar to [insertion sort](../Insertion%20Sort/), but the difference is
1010

1111
It works as follows:
1212

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.
1515
- Go to index 1.
1616
- 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.
1818
- 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.
2121

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.
2323

2424
## An example
2525

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.
2727

2828
Initially, the sorted portion is empty:
2929

@@ -43,7 +43,7 @@ Again, we look for the lowest number, starting from the `|` bar. We find `4` and
4343
[ 3, 4 | 5, 8, 6 ]
4444
* *
4545

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:
4747

4848
[ 3, 4, 5 | 8, 6 ]
4949
*
@@ -52,7 +52,7 @@ This process repeats until the array is sorted. Note that everything to the left
5252

5353
[ 3, 4, 5, 6, 8 |]
5454

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).
5656

5757
## The code
5858

@@ -90,27 +90,27 @@ selectionSort(list)
9090

9191
A step-by-step explanation of how the code works:
9292

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.
9494

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.
9696

9797
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.
9898

9999
4. This is the inner loop. It finds the lowest number in the rest of the array.
100100

101101
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.
102102

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!)
104104

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.
106106
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.
108108

109109
## Performance
110110

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 .
112112

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)**.
114114

115115
## See also
116116

0 commit comments

Comments
 (0)
0