[개념] 버블정렬, 선택정렬

선택정렬 (Selection Sort)

선택정렬은 배열중에 가장 작은 원소들을 왼쪽부터 채워나가면서 숫자를 정렬하는 방법입니다.

최소원소를 찾은 후 

=> 최소원소를 맨 왼쪽원소와 교환(즉, 왼쪽부터 정렬된 원소로 채워집니다.)

=> 왼쪽원소를 제외하고 원소가 하나남을때 까지 이단계를 반복

 

선택정렬의 비교횟수를 구해보면

1단계 => n개의 원소 비교

2단계 => n-1 개의 원소 비교

3단계 => n-2 개의 원소 비교

....

를 하여 비교 횟수는

n(n-1) /2 가 됩니다.

즉, 시간복잡도는 O(n^2)이 됩니다.

 

		for(i=0; i<num.length-1; i++) {
			for (j=i+1;j<num.length;j++) {
				if(num[i]>num[j]) { //오름차순
					temp=num[i];
					num[i]=num[j];
					num[j]=temp;
				}
			}
		}

 

 

---

버블정렬 (Bubble Sort)

 

 

 

배열을 순차탐색하여 i, i+1번째 요소를 비교하여 큰 것을 뒤로 이동 합니다.
위 과정이 1번 처리되는 경우 가장 큰 수가 배열 마지막에 위치 합니다.

다음 탐색부터는 마지막요소는 안해도 됩니다. ( 그래서 내부에 있는 for문은 arr.length - i 까지만 탐색)

 

public static void bubbleSort(int[] arr) {
    for(int i = 0; i < arr.length; i++) {
        for(int j = 0 ; j < arr.length - i - 1 ; j++) {
            if(arr[j] > arr[j+1]) {
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

 

 

 

 

 

출처

https://cornswrold.tistory.com/14

https://javaplant.tistory.com/16