본문 바로가기
Algorithm/Study

Swift Sorting Algorithm Note

by HaningYa 2021. 1. 13.
728x90

https://brilliant.org/wiki/sorting-algorithms/

1. 선택 정렬

  1. 정렬되지 않은 맨 앞에서 부터 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾는다.
  2. 가장 작은 값을 찾으면 그 값을 현재 인덱스와 바꿔준다.
  3. 다음 인덱스에서 위 과정을 반복한다.

시간 복잡도: O(n^2)

공간 복잡도: O(n)

5 2 3 1

1 5 2 3 

1 2 5 3

1 2 3 5

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        for i in 0..<nums.count {
            for j in i+1..<nums.count {
                if nums[i] >= nums[j] {
                    let tmp = nums[i]
                    nums[i] = nums[j]
                    nums[j] = tmp
                }
            }
        }
        return nums
    }
}


  func selectionSort(_ nums: [Int]) -> [Int] {
        var nums = nums
        var tmp = 0
        for i in 0..<nums.count {
            var minIndex = i
            for j in i+1..<nums.count {
                if nums[minIndex] > nums[j] {
                    minIndex = j
                }
               
                // if nums[i] < nums[j] {
                //     //sorted
                // }else {
                //     //unsorted -> swap
                //     let tmp = nums[i]
                //     nums[i] = nums[j]
                //     nums[j] = tmp
                // }
            }
            tmp = nums[minIndex]
            nums[minIndex] = nums[i]
            nums[i] = tmp
        }
        return nums
    }
  • 시간 복잡도 O(N^2)인 알고리즘 중에서 선택정렬은 버블정렬보다 항상 우수하다.
    버블은 모든 수끼리 한번씩 하는데 (둘둘둘) 선택은 첫번째 자리수, 두번째 자리수 이런식으로 하니 대입연산도 적게 일어남
  • 삽입정렬은 k번째 반복 이후 첫번째 k 요소가 정렬된 순서로 온다는 점이 유사하나 
    선택정렬은 k+1번째 요소를 찾기위해 배열 전체를 탐색하지만 삽입정렬은 k+1번째 요소를 배치하는데 필요한 만큼의 요소만 탐색하니훨씬 효율적이다.
  • 합병정렬보다 작은 배열 요소에서 빠르다.(10개~20개 미만)

 

2. 삽입 정렬

정렬되지 않은 부분에서 요소를 꺼내 정렬된 부분에 맞는 위치에 집어넣어준다.

  1. 두번째 인덱스 부터 시작하고 현재 인덱스는 별도의 변수에 저장하고 비교 인덱스를 현재 인덱스의 -1 로 설정한다.
  2. 별도로 저장해둔 insert를 위한 변수와 비교 인덱스 값을 비교한다.
  3. 삽입 변수의 값이 더 작으면 현재 현재 인덱스로 비교 인덱스 값을 저장해주고 비교 인덱스를 -1하여 반복한다.
  4. insert 변수가 더 크면 비교 인덱스+1 에 insert 변수를 저장한다.

시간복잡도: 역정렬 O(n^2), 이미 정렬된 경우 O(n)

공간 복잡도 O(n)

5 2 3 1

2 5 3 1

2 3 5 1

1 2 3 5

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        for i in 1..<nums.count{
            var key = nums[i]
            var j = i-1
            while j>=0 && key < nums[j] {
                let tmp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = tmp
                j -= 1
            }
            nums[j+1] = key
        }
        return nums
    }
}

    func insertionSort(_ nums: [Int]) -> [Int] {
        var nums = nums
        var counter = 0
        for i in 1..<nums.count {
            var j = i-1 //sorted subset last index
            var value = nums[i] //unsorted subset first element
            
            //insert value into sorted subset
            while j >= 0 && value < nums[j] {
                // j moves forwards until reaches 0
                // && compare value with last subset value
                // value < nums[j]
                // if value < last subset value
                //shift value position forward
                
                /** 
                2 7 | 4 1 5 3
                2 7 4 | 1 5 3
                value = 4, last subset value = 7
                if 4 < 7 (value < last subset value)
                shift forward
                2 4 7 | 1 5 3
                **/
                nums[j+1] = nums[j]
                j -= 1
                
                // let tmp = nums[j]
                // nums[j] = nums[j+1]
                // nums[j+1] = tmp
                // j -= 1
            }
            
            nums[j+1] = value
        }
        return nums
    }

3. 버블 정렬

연속된 두개의 index를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬

  1. 두번째 인덱스 부터 시작한다. 현재 인덱스와 이전 인덱스 비교한다.
  2. 이전 인덱스가 크면 바꿔준다.
  3. 현재 인덱스가 크면 교환하지 않고 다음 연속 배열값을 비교한다.
  4. 전체 배열의 크기 - 현재까지 순환한 바퀴 수 만큼 반복한다.

시간복잡도: O(n^2)

공간 복잡도 O(n)

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        for _ in 0..<nums.count {
            for j in 1..<nums.count {
                if nums[j-1] > nums[j] {
                    let tmp = nums[j]
                    nums[j] = nums[j-1]
                    nums[j-1] = tmp
                }
            }
        }
        return nums
    }
}

[5, 2, 3, 1]
[2, 5, 3, 1]
[2, 3, 5, 1]
[2, 3, 1, 5]
[2, 3, 1, 5]
[2, 1, 3, 5]
[2, 1, 3, 5]
[1, 2, 3, 5]
[1, 2, 3, 5]
[1, 2, 3, 5]
[1, 2, 3, 5]
[1, 2, 3, 5]
[1, 2, 3, 5]

4. 합병 정렬

분할 정복 방식

시간 복잡도 O(NlgN) (분할 lgN, 합병, N)

공간 복잡도 O(2N)

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        if nums.count <= 1 {
            return nums
        }
        
        var leftList : [Int] = []
        var rightList : [Int] = []
        
        let mid = nums.count/2
        leftList += nums[0..<mid]
        rightList += nums[mid..<nums.count]
        
        var left = sortArray(leftList)
        var right = sortArray(rightList)
        
        return merge(left, right)
    }
    
    func merge(_ left: [Int],_ right : [Int]) -> [Int] {
        var left = left
        var right = right
        var result: [Int] = []
        while !left.isEmpty && !right.isEmpty {
            let value = left[0] < right[0] ? left.removeFirst() : right.removeFirst()
            result += [value]
        }
        if !left.isEmpty {
            result += left
        }
        if !right.isEmpty {
            result += right
        }
        return result
    }
}





    //merge sort: split
    func mergeSort(_ nums: [Int]) -> [Int] {
        var nums = nums
        // split until array count is 1
        guard nums.count > 1 else{
            return nums
        }
        let leftArr = Array(nums[0..<nums.count/2])
        let rightArr = Array(nums[nums.count/2..<nums.count])
        
        
        
        return merge(mergeSort(leftArr), mergeSort(rightArr))
    }
    //merge sort: merge
    func merge(_ leftArr :[Int] ,_ rightArr : [Int] ) -> [Int] {
        var mergedArr : [Int] = []
        var leftArr = leftArr
        var rightArr = rightArr
        
        while leftArr.count > 0 && rightArr.count > 0 {
            if leftArr.first! < rightArr.first! {
                mergedArr.append(leftArr.removeFirst())
            }else{
                mergedArr.append(rightArr.removeFirst())
            }
        }
        // 한쪽에만 숫자가 있는경우 다른쪽은 이미 정렬되있는 뜻이니 전체 append
        return mergedArr + leftArr + rightArr
    }

5. 퀵 정렬

분할정복, pivot을 기준으로 작은값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        if nums.count < 1 {return nums}
        let pivot = nums[nums.count/2]
        let less = nums.filter{$0 < pivot}
        let equal = nums.filter{$0 == pivot}
        let greater = nums.filter{$0 > pivot}
        let ans = sortArray(less) + equal + sortArray(greater)
        return ans
    }
    
   
}

시간 복잡도 O(NlgN) / 이미 정렬되었을때 혹은 pivot이 계속 최소, 최대 값일 경우 최악 O(N^2)

(분할 lgN, 합병, N)

leetcode.com/problems/sort-an-array/

 

Sort an Array - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        // selectionSort(nums)
        // insertionSort(nums)
        // bubbleSort(nums)
        // mergeSort(nums)
        quickSort(nums)
    }
    
    
    
    //selection sort
    func selectionSort(_ nums: [Int]) -> [Int] {
        var nums = nums
        var tmp = 0
        for i in 0..<nums.count {
            var minIndex = i
            for j in i+1..<nums.count {
                if nums[minIndex] > nums[j] {
                    minIndex = j
                }
               
                // if nums[i] < nums[j] {
                //     //sorted
                // }else {
                //     //unsorted -> swap
                //     let tmp = nums[i]
                //     nums[i] = nums[j]
                //     nums[j] = tmp
                // }
            }
            tmp = nums[minIndex]
            nums[minIndex] = nums[i]
            nums[i] = tmp
        }
        return nums
    }
    
    //insertion sort
    func insertionSort(_ nums: [Int]) -> [Int] {
        var nums = nums
        var counter = 0
        for i in 1..<nums.count {
            var j = i-1 //sorted subset last index
            var value = nums[i] //unsorted subset first element
            
            //insert value into sorted subset
            while j >= 0 && value < nums[j] {
                // j moves forwards until reaches 0
                // && compare value with last subset value
                // value < nums[j]
                // if value < last subset value
                //shift value position forward
                
                /** 
                2 7 | 4 1 5 3
                2 7 4 | 1 5 3
                value = 4, last subset value = 7
                if 4 < 7 (value < last subset value)
                shift forward
                2 4 7 | 1 5 3
                **/
                nums[j+1] = nums[j]
                j -= 1
                
                // let tmp = nums[j]
                // nums[j] = nums[j+1]
                // nums[j+1] = tmp
                // j -= 1
            }
            
            nums[j+1] = value
        }
        return nums
    }
    
    func bubbleSort(_ nums: [Int]) -> [Int]  {
        var nums = nums
        for _ in 0..<nums.count {
            for j in 1..<nums.count {
                if nums[j] < nums[j-1] {
                    // let tmp = nums[j]
                    // nums[j] = nums[j-1]
                    // nums[j-1] = tmp
                }
            }
        }
        return nums
    } 
    //merge sort: split
    func mergeSort(_ nums: [Int]) -> [Int] {
        var nums = nums
        // split until array count is 1
        guard nums.count > 1 else{
            return nums
        }
        let leftArr = Array(nums[0..<nums.count/2])
        let rightArr = Array(nums[nums.count/2..<nums.count])
        
        
        
        return merge(mergeSort(leftArr), mergeSort(rightArr))
    }
    //merge sort: merge
    func merge(_ leftArr :[Int] ,_ rightArr : [Int] ) -> [Int] {
        var mergedArr : [Int] = []
        var leftArr = leftArr
        var rightArr = rightArr
        
        while leftArr.count > 0 && rightArr.count > 0 {
            if leftArr.first! < rightArr.first! {
                mergedArr.append(leftArr.removeFirst())
            }else{
                mergedArr.append(rightArr.removeFirst())
            }
        }
        // 한쪽에만 숫자가 있는경우 다른쪽은 이미 정렬되있는 뜻이니 전체 append
        return mergedArr + leftArr + rightArr
    }
    
    //quick sort with cache
    func quickSort(_ nums : [Int]) -> [Int] {
        var nums = nums
        if nums.count < 1 {
            return nums
        }
        let pivot = nums[nums.count/2]
        let less = nums.filter{$0 < pivot}
        let equal = nums.filter{$0 == pivot}
        let greater = nums.filter{$0 > pivot}
        return quickSort(less) + equal + quickSort(greater)
    }

자료구조 이용하는 정렬

6. 힙 정렬

joycestudios.tistory.com/59

7. Count 정렬

bowbowbow.tistory.com/8

8. Radix 정렬

9. Introsort (swift sorting before Swift5)

10. TimSort (current swift sorting algorithm)

 

알고리즘 최선 평균 최악
삽입정렬 O(n) O(n^2) O(n^2)
선택정렬 O(n^2) O(n^2) O(n^2)
버블정렬 O(n^2) O(n^2) O(n^2)
셸정렬 O(n) O(n^1.5) O(n^1.5)
퀵정렬 O(nlogn) O(nlogn) O(n^2)
히프정렬 O(nlogn) O(nlogn) O(nlogn)
합병정렬 O(nlogn) O(nlogn) O(nlogn)
기수정렬 O(dn) O(dn) O(dn)

안정된 정렬

  • 합병 정렬
  • 삽입 정렬
  • 기수 정렬
  • Tim 정렬
  • 버블 정렬

불안정 정렬

  • 힙정렬
  • 퀵정렬

reference

  • hsp1116.tistory.com/33
  • minsone.github.io/programming/merge-sort-in-swift
  • hyerios.tistory.com/70
  • riptutorial.com/ko/algorithm/example/2783/%EC%A0%95%EB%A0%AC%EC%9D%98-%EC%95%88%EC%A0%95%EC%84%B1
728x90
저작자표시

'Algorithm > Study' 카테고리의 다른 글

이진트리 연산  (0) 2021.01.16
이진트리 순회  (0) 2021.01.16
Swift 다항식 덧셈  (0) 2020.09.11
6 Recursive Pattern  (0) 2020.09.11
Swift - Graph Implemetation  (0) 2020.07.20

관련글

댓글

티스토리툴바