Bubble, Selection, Insertion - Sort

Bubble Sort

• 인접한 두 숫자를 비교해서 조건에 들어맞으면 자리 바꿈
• 6개의 숫자가 있다면 첫 번째 숫자는 다섯 번만 비교하면 됨
• 참고로 merge sort는 copy를 발생시키고 bubble sort는 그렇지 않기 때문에, 버블 소트는 space complexity가 O(1).

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

Selection Sort

• 버블 소트와 같이 셀렉션 소트 역시 인덱스를 필요로 하지만
• 셀렉션 소트는 가장 작은 값을 가진 인덱스를 찾아 minIndex라는 변수에 저장한다.

public void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }

Insertion Sort

• 인서션 소트는 언제나 두 번째 값, 즉 인덱스 1부터 시작한다. - 예를 들자면 처음 루프를 돌 때 인덱스 1의 값이 인덱스 0의 값보다 작으면 인덱스 0의 값과 인덱스 1의 값을 바꾼다.

public void insertionSort(int[] array) {
		// insertionSort는 index1, 즉 두 번째 숫자부터 시작한다
		for(int i = 1; i < array.length; i++) {
			int temp = array[i];
			int j = i-1;
			while(j>-1 && temp < array[j]) {
				// 조건절에 주의
				// j>-1가 &&의 뒤 쪽에 있으면 오류난다 
				array[j+1] = array[j];
				array[j] = temp;
				j--;
			}
		}
	}

Main

public static void main(String[] args) {
		BubbleSort bu = new BubbleSort();
		int[] myArray = {4,2,6,5,1,3};
		//bu.bubbleSort(myArray);
		//bu.selectionSort(myArray);
		bu.insertionSort(myArray);
		System.out.println(Arrays.toString(myArray));   

	}