[알고리즘] 3강 기본적인 정렬 알고리즘 정리

3강 기본적인 정렬 알고리즘 정리

정렬 알고리즘 종류

• simple, slow
  bubble sort
  insertion sort
  selection sort
• quick
  quick sort
  merge sort
  heap sort
• O(N)
  radix sort

1. Selection Sort (선택 정렬)

선택 정렬은 배열의 값 중 하나를 선택해 기준으로 두고 정렬하는 알고리즘이다.

data[Int] 변수가 있을 때

1. 배열의 data[i]을 기준으로 두어 변수에 값을 저장한다. (data[i]을 배열의 min 값으로 예상)
2. min 값과 data[i+1] 값을 비교하여 data[i+1] > min 이면 min에 data[i+1] 값을 대입한다.
3. data[i] 과 min 값을 swap 한다.
4. 1~3번까지 반복한다.

    // 1. 선택정렬
    func selectionSort(data: [Int]) -> [Int] {
        var result = data
        var location = 0
        var min: Int
        for i in 0 ..< result.count {
            min = result[i]
            location = i
            for j in i+1 ..< result.count {
                    if min > result[j] {
                        min = result[j]
                        location = j
                    }
            }
            result.swapAt(i, location)
        }
        return result
    }

2. Bubble Sort (버블 정렬)

인접한 두 인덱스의 값을 비교해가며 정렬하는 알고리즘이다.

data[Int] 변수가 있을 때

1. 배열의 data[j] 와 data[j+1] 값을 비교한다

2. data[j] > data[j+1] 이면 swap 한다.

3. 1~2번을 반복한다.

    // 2. 버블정렬
    func bubbleSort(data: [Int]) -> [Int] {
        var result = data
   
        for i in 0..<result.count {
            for j in 0..<result.count-1 {
                if result[j] > result[j+1] {
                    result.swapAt(j, j+1)
                }
            }
        }
        return result
    }