버블 정렬(Bubble sort)과 교환 정렬(Exchange sort)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① 버블 정렬(bubble sort)과 교환 정렬은 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘 중 하나이다.

  ㉠ 정렬의 가장 이상적인 상황에서의 시간 복잡도는 O(N)이다.

    ⓐ 모든 항목이 정렬되어 있을 경우 단순 탐색만 진행하면 되기 때문에 O(N)의 시간 복잡도를 갖는다.

  ㉡ 버블 정렬과 교환 정렬의 최악의 상황에서 시간 복잡도는 O(N^2)이다.

② 버블 정렬과 교환정렬의 기본적인 작동원리는 인접한 두 수를 비교해 위치를 바꾸는 것으로 동일하다.

  ㉠ 버블 정렬의 작동 원리는 다음과 같다.

    ⓐ 선택된 배열의 첫 번째 요소와 두 번째 요소를 비교한다. 만약 정렬되어 있지 않다면 둘의 위치를 바꾼다.

    ⓑ 인접한 다음 쌍으로 이동하고 배열의 끝에 도달할 때까지 ⓐ를 반복한다.

    ⓒ ⓑ을 더이상 교환이 이루어지지 않을 때까지 반복한다.

  ㉡ 버블 정렬의 의사 코드(psuedo code)는 다음과 같다.

 

  ㉢ 교환 정렬의 작동 원리는 다음과 같다.
    ⓐ 초기 피벗 인덱스(pivot index)를 0으로 한다.

    ⓑ 배열의 정렬되지 않은 부분에서 가장 작은 값을 찾는다.

    ⓒ 피벗 인덱스에 위치한 요소와 가장 작은 요소를 교환한다.

    ⓓ 피벗 인덱스를 1 증가시키며, 배열의 크기보다 1 작을 때까지 ⓑ, ⓒ를 반복한다.

  ㉣ 교환 정렬의 의사 코드는 다음과 같다.

 

③ 버블 정렬의 시간 복잡도는 O(N^2)이다.

  ㉠ 가장 단순하게 생각해보면 최댓값을 찾기 위해 매 탐색마다 인접한 한 쌍을 두 요소를 비교한다.

  ㉡ i 는 0부터 N - 1까지 가능하다.

  ㉢ 어떠한 k에 대해서 T는 무조건 kN^2에 대해 무조건 같거나 작기 때문에 교환 정렬의 시간 복잡도는 O(N^2)이다.

  ㉣ N을 키울 수록 대략 N^2에 비례하게 커짐을 알 수 있다.

 

④ 교환 정렬의 시간 복잡도는 O(n^2)이다.

  ㉠ 가장 단순하게 생각해보면 최솟값을 찾기 위해 매 탐색마다 피봇과 N-i개의 배열의 요소를 비교한다.

  ㉡ i 는 0부터 N - 1까지 가능하다.

 

  ㉢ 어떠한 k에 대해서 T는 무조건 kN^2에 대해 무조건 같거나 작기 때문에 교환 정렬의 시간 복잡도는 O(N^2)이다.

  ㉣ N을 키울 수록 대략 N^2에 비례하게 커짐을 알 수 있다.