6. Sorting
O(N²): Bubble Sort, Selection Sort, Insertion Sort
O(NlogN): Quick Sort, Merge Sort, Heap Sort
6. 1. Bubble Sort — O(N²)
Compares the first digit of the array with the value of the next digit, and if the previous value is greater, the position of the digit is changed. Repeat the length of the array to compare subscripts from the back.
func boubbleSort (_ data:[Int],_ n:Int) -> [Int]{
var data = data
for i in 0...n-2 {
let last = n-i
for j in 0...last-1 {
if data[j] > data[j+1] {
let temp = data[j]
data[j] = data[j+1]
data[j+1] = temp
}
}
}
return data
}boubbleSort([7,5,4,2,3,9], 5)
6. 2. Insertion Sort — O(N²)
If the value at the very end of the array is less than the value of the preceding digit in the place, exchange the two values. If the changed value is less than the previous value, exchange the two values. If no exchange is made, repeat with the value at the back of the array.
func insertionSort (_ data:[Int],_ n:Int) -> [Int]{
var data = data
var end = n-1
for i in (0...n-1).reversed() {
for j in (0...end).reversed() {
if data[i] < data[j] {
let temp = data[i]
data[i] = data[j]
data[j] = temp
}
}
end -= 1
}
return data
}insertionSort([7,5,4,2,3,9], 6)
6. 3. Selection Sort — O(N²)
Find the largest value in the array and exchange it with the value at the end of the array. Then repeat with the array except the last one.
func selectionSort (_ data:[Int],_ n:Int) -> [Int]{
var data = data
var end = n-1
for i in 0...end {
var largestIndex = 0
for j in 0...end {
if data[j] > data[largestIndex] {
largestIndex = j
}
}
let temp = data[largestIndex]
data[largestIndex] = data [n-1-i]
data[n-1-i] = temp
end -= 1
}
return data
}selectionSort([7,5,4,2,3,9], 6)
6. 4. Quick Sort — O(NlogN)
Quick sorting is the best sorting technique among multiple sorting techniques.
(Recursion and Divide and Quanquer techniques are used.)
- Determine the pivot value from the current data D Suppose this value is the leftmost value in the current data range.
- Once the pivot value has been determined, it should be divided into two independent parts centered on it. (D1), which is smaller than the pivot value on the left side of the pivot value, and only values larger than the pivot value, on the right side of the pivot value (D2). This allows the D1 and D2 parts to be independent of each other, reducing the overall problem to two independent problems.
- If you divide into D1 and D2, you can recursively process the above two steps.
- If you can not reduce the size of the data any more, the current values are returned.
var data = [5,2,7,4,1,10,6,3,8,9]
func quickSort(_ left: Int,_ right: Int){
if (left < right){
var pivot = partition(left, right)
quickSort(left, pivot-1)
quickSort(pivot+1, right)
}
}
func partition(_ left: Int,_ right: Int) -> Int {
var i = left
for j in (left + 1)...(right + 1) {
if data[j] < data[left] {
i += 1
(data[i], data[j]) = (data[j], data[i])
}
}
(data[i], data[left]) = (data[left], data[i])
return i
}quickSort(0,9)
6. 5. Merge Sort— O(NlogN)
- Split: Halves the array in which the data is stored
- Conquer: Arrange each array cyclically
- Merging: Combining two arrays
The basic merge sort starts with two sorted data A, B and an array C for merging the two data. The i, j, and count variables are used to display the current comparison data location of the array A, B, and C, and the initial value is set to the initial position of each variable.
func merge(left:[Int],right:[Int]) -> [Int] {
var mergedList = [Int]()
var left = left
var right = right
while left.count > 0 && right.count > 0 {
if left.first! < right.first! {
mergedList.append(left.removeFirst())
} else {
mergedList.append(right.removeFirst())
}
}
return mergedList + left + right
}
func mergeSort(list:[Int]) -> [Int] {
guard list.count > 1 else {
return list
}
let leftList = Array(list[0..<list.count/2])
let rightList = Array(list[list.count/2..<list.count])
return merge(left: mergeSort(list:leftList), right: mergeSort(list:rightList))
}print(mergeSort(list:[5,2,7,4,1,10,6,3,8,9]))
