정렬 알고리즘(sorting algorithm) - 버블 정렬(bubble sort)

정렬 알고리즘

n개의 숫자가 주어졌을때 이를 오름차순 / 내림차순으로 정렬하는 알고리즘

다양한 알고리즘이 있으며, 알고리즘에 따라 시간 복잡도가 다르다

2. 버블 정렬(bubble sort)

•정렬되지 않은 범위의 맨 앞부터 맨 뒤까지 순차적으로 연속된 인덱스의 값을 비교하여 정한 기준에 의해 정렬하는 방식

    - 오름차순으로 정렬할 경우 연속된 인덱스의 값을 비교하여 작은 수가 앞으로, 큰 수가 뒤로 정렬

    - 내림차순으로 정렬할 경우 연속된 인덱스의 값을 비교하여 큰 수가 앞으로, 작은 수가 뒤로 정렬

•반복문의 첫 바퀴가 지나면 가장 큰/작은 수가 맨 뒤로 이동하게 된다. (오름차순의 경우 가장 큰 수, 내림차순의 경우 가장 작은 수)

•이중 반복문을 사용하게되며, 바깥의 반복문은 (n - 1)번 반복, 안쪽 반복문은 (n - 바깥 반복문의 반복된 횟수)만큼 반복한다.

•정렬 방식

•시간 복잡도

탐색(비교)는 4, 3, 2, 1 번 실행 되었으므로

n-1, n-2, n-3, n-4 번

-> n-1, n-2, ..., 1 이라 볼수있다.

즉 총 비교 수는 (n-1) + (n-2) + ... + 1

= ( (n-1) * (n - 1 + 1) )  / 2

= ( n * (n - 1) ) / 2 

= (n^2 - n) / 2

빅오표기법으로 표기하면

O(n^2) 이 된다.

•공간 복잡도

한개의 배열 [5, 7, 4, 2, 1]만 사용하므로

n개의 원소가 들어간 배열의 경우

O(n) 이 된다.