거품정렬과 선택정렬 - 알고리즘

Bubble Sort 가장 간단한 정렬 알고리즘

거품 정렬 즉 Bubble Sort는 가장 기초적인 정렬 알고리즘이다.

서로 인접한 2가지 원소를 비교하고, 조건에 맞지 않다면 자리를 교환하는 알고리즘 입니다.

버블솔트 구현 못하면 주니어

2중 포문으로 구성되어 있으며, 첫번째 포문의 1번째때, 첫번재와 두번째원소를 비교하고, 두번째와 세번째 원소를 비교하고 마지막-1번째와 마지막번째를 비교하는 식으로 구성됩니다. 

1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

 

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {       // 1.
		for(int j= 1 ; j < arr.length-i; j++) { // 2.
			if(arr[j-1] > arr[j]) {             // 3.
                // swap(arr[j-1], arr[j])
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

 

시간복잡도는 2중포문으로 n-1 + n-2 + n-3 ... +1 이므로 n(n-1)/2로 O(n^2)입니다.

공간복잡도는 해당 배열에서만 일어나므로 O(n)으로 동일합니다.

 

선택 정렬

Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다. 거품 정렬이 가장 뒤에 나올 원소들을 차례대로 정리하는 것이라면, 선택정렬은 정렬시 해당위치에 와야할 원소를 선택하는 것입니다.

1. 주어진 subArray중 최솟값을 찾습니다.
2. 가장 앞에 값과 교체합니다.
3. 맨 처음 위치를  뺀 나머지 배열을 같은 방법으로 교체합니다.

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

 

데이터의 개수가 n개라고 했을 때,

 

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
•   ...
• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸립니다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일합니다.

 

공간복잡도는 동일하게 O(n)입니다.