정렬 - 버블정렬

버블 정렬

버블 정렬은 이웃하는 값들의 크기를 비교하여 자신이 원하는 정렬 방식 (오름차순/내림차순) 에 부합하도록 해당 요소들의 자리를 변경하고,

이 비교 작업이 배열을 한 번, 한 뱡항으로 훑게 되면 결국 마지막 요소는 가장 큰/작은 값임을 보장받게 된다.

따라서, 이후 이 마지막 요소를 제외하고 다시 처음부터 비교 작업을 진행해가는 방식이다.

이웃한 요소를 비교하고 필요시 곧바로 swap 한다는 특징이 있다.

generateRandomArray, printArray, swap

static int arrayLength = 20;
int *myArray = generateRandomArray(arrayLength); // 랜덤으로 값이 초기화된 배열 생성

printArray(myArray, arrayLength); // 정렬 전 배열 출력

for (int i = 0; i < arrayLength; i++) { // 배열의 첫 번째 요소부터 뒤쪽으로 탐색하는데,
    for (int j = i; j < arrayLength; j++) { // 현재 위치부터 뒤쪽으로 배열의 끝까지 탐색하면서,
        if (myArray[i] > myArray[j]) { // 만일 현재 위치의 값이 뒤쪽의 값보다 크다면,
            swap(&myArray[i], &myArray[j]); // 둘의 위치를 교환한다.
        }
    }
}

printArray(myArray, arrayLength); // 정렬 후 배열 출력

작은 것부터, 점점 커지게, 오름차순으로 정렬한 예제이다.

2중 for 문 내부에 크기 비교 후 곧바로 swap 하는 구조가 특징이다.

이러한 버블 정렬은, 물론 내부의 for문은 완전히 array Size 만큼 돌지는 않고, 평균 (arraySize-1)/2 번만큼 돌기는 하지만, n만큼의 2중 for문이라고 볼 수 있으니

O(N²) 의 복잡도를 가지게 된다.