정렬 알고리즘- 버블, 선택, 삽입 정렬

슆공부·2022년 7월 26일
0

1. 버블 정렬

① 두 인접한 데이터를 비교한다
② 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 둘의 자리를 바꿔준다

이렇게 한번으로 정렬 안되면 전체 정렬이 될 때까지 반복한다.

구현하기

1-1.
인접 데이터끼리 비교하며 swap하는 작업 (스캔 작업)은 총 (탐색하는 요소의 갯수 - 1) 만큼 진행하면된다.

2-1.
한번의 스캔은 끝났지만 전체 정렬까지 반복해야하는데,
스캔 작업을 한 번 할 때마다 큰 값부터 하나씩 정렬될 테니, 스캔 작업을 최대 (배열 요소의 갯수 - 1) 만큼 진행하면 전체 배열이 정렬되는 것이다.
10개 중 9개 정렬하면 제일작은 값 하나는 자동으로 0 인덱스에 들어있게 될 것이니 count - 1 을 하면 된다.

  1. 스캔 작업의 실행 횟수에 따라, 스캔 작업 시 탐색하는 요소의 수가 줄어든다. 마직막부터 한개씩 정렬되는 것이니 그렇겠지?

코드로 구현하기

func bubbleSort(_ array: inout [Int]) {
    for index1 in 0..<(array.count - 1) {                // 스캔 작업 반복
        var isSwap = false
        for index2 in 0..<((array.count - index1) - 1) { // 스캔 작업(인접 인덱스 비교 및 swap 반복) : (탐색하려는 요소의 갯수) - 1 => 탐색하려는 요소의 갯수는 스캔 횟수에 따라 차감됨(스캔 횟수만큼 정렬되어 있을테니)
            if array[index2] > array[index2 + 1] {
               array.swapAt(index2, (index2 + 1))
                isSwap = true
            }
        }
        if isSwap == false { return }
    }
}

여기서 isSwap은??
만약 스캔할 때 swap이 전혀 일어나지 않으면 이전 index값이 다음것보다 클 수가 없다는 의미로 모두 정렬이 되었다는 뜻이니 리턴으로 끝내버리면 된다.

  • 시간 복잡도
    배열의 요소 갯수만큼 도는 반복문 안에 요소 갯수만큼 도는 반복문이 돌기 때문에 O(n^2)으로 쉽고 간단하지만 느린 알고리즘이다.

선택 정렬

① 데이터 중 가장 작은 값을 찾는다
② 찾은 값을 데이터 맨 앞 값과 교체한다
③ 맨 앞 데이터를 제외하고 위 과정을 반복한다


이렇게 0번 index부터 가장 작은 값으로 채워나가는 정렬 방법이다.

구현하기

  1. 최소값 찾는 스캔은 기준인 인덱스 +1 ..< 배열요소개수 만큼 반복하면된다.
  2. 전체가 정렬되도록 index+1 하면서 반복해야한다.
  3. 맨앞부터 정렬되니까 배열개수-1 만큼 반복하면된다.
func selectionSort(_ array: inout [Int]) {
    for stand in 0..<(array.count - 1) {                // 스캔 작업 반복
        var minIndex = stand
        for index in (stand + 1)..<array.count {        // 스캔 작업 (stand가 0이면 1번 index부터 마지막 Index까지 돌며 최소값을 찾아야 하니까)
            if array[index] < array[minIndex] {
                minIndex = index
            }
        }
        array.swapAt(stand, minIndex)
    }
}
  • 시간 복잡도
    배열 개수만큼 도는 반복문 내에 또 개수만큼도는 반복문이 있어서 O(n2)로
    버블과같이 쉽고 간단하지만 느리다!

삽입 정렬

① 정렬은 두 번째 요소부터 시작한다
② 기준이 되는 index와 인접한 index부터 비교하며 삽입한다
③ 삽입이 끝나면, 기준 index의 다음 index를 기준으로 잡는다

=>
기준 index는 1부터 시작하며, 기준 index에 인접한 이전 index부터,

기준 index의 값보다 작은 놈을 만날 때까지 swap하다가, 작은놈을 만나면 종료

한 번 스캔이 끝나면, 기준 index의 다음 index를 기준으로 잡고 다시 스캔 진행

구현하기

func insertionSort(_ array: inout [Int]) {
    for stand in 1..<array.count {
        for index in stride(from: stand, to: 0, by: -1) {
            if array[index] < array[index - 1] {
                array.swapAt(index, index - 1)
            } else {
                break
            }
        }
    }
}

stride 메서드는 to 이전까지만 반복이 된다고 한다!

  • 시간복잡도
    반복문안에 반복문 있어서 이것도 O(n2)로 느리다.
    빅오는 최악의 경우를 나타내서 같지만 버블, 선택보다는 빠르다고는 한다.

https://babbab2.tistory.com/97?category=908012
https://babbab2.tistory.com/98?category=908012

0개의 댓글