[CS50 4주차] Bubble Sort & Selection Sort

Bubble Sort

• 서로 인접한 2개의 원소를 비교하여 정렬하는 알고리즘
  • 2개의 원소의 크기를 비교했을때 (오름차순)올바르지 않으면 두 원소를 교환

• 1번 원소와 2번 원소를 비교, 2번 원소와 3번 원소를 비교, .... (마지막 원소 - 1) 과 마지막 원소를 비교하면서 자료들을 정렬.
• step 1 - step 6까지 1회전 정렬하고 나면 가장 큰 수의 원소가 맨 뒤로 이동. 2회전 정렬때는 가장 큰 원소를 제외.
• n개의 원소에 대해서 버블 정렬을 한번 수행할 때마다 n번째의 원소가 제 자리를 찾게되고, 그 다음 정렬에서는 n-1개의 원소를 정렬해 주면 됨.

🔽 Bubble Sort 의사코드

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

🔽 Bubble Sort 구현 (C언어) (오름차순)

#include <cs50.h>
#include <stdio.h>
#define SIZE 5

void bubble_sort(int arr[], int n)
{
    int temp;
    for(int i = 0; i < n - 1; i++){
    	for(int j = 0; j < (n - i) -1; j++){
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main(void)
{
    int n = 5;
    int arr[5] = { 7, 5, 4, 1, 3 };

    bubble_sort(arr,n);

    for (int i = 0; i < n; i++)
    {
        printf("%d\n",arr[i]);
    }
}

🔽 Bubble Sort 구현 (C언어) (내림차순)

#include <cs50.h>
#include <stdio.h>
#define SIZE 5

void bubble_sort(int arr[], int n)
{
  int temp;
  for (int i=n-1; i>0; i--){

      for (int j=0; j<i; j++){

      if (arr[j]<arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
		       }
		     }
	   }
	}

int main(void)
{
    int n = 5;
    int arr[5] = { 7, 5, 4, 1, 3 };

    bubble_sort(arr,n);

    for (int i = 0; i < n; i++)
    {
        printf("%d\n",arr[i]);
    }
}

🔽 Bubble Sort 시간 복잡도 

중첩 루프를 돌고 루프는 n-1번 n-2번 반복 됨

$(n-1)*(n-2)=n^2-3n+2$ 번의 비교 및 교환이 필요.

버블정렬 실행시간의 상한

$\therefore T(n) = O(n^2)$

버블정렬 실행시간의 하한 >> 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교해야함

$\therefore T(n) = \Omega(n^2)$