[정렬 알고리즘] 버블정렬, 선택정렬, 삽입정렬

정렬 알고리즘  

• 버블정렬 Bubble Sort
• 선택정렬 Selection Sort
• 삽입정렬 Insertion Sort

 

 

버블정렬 Bubble Sort

출처 : 위키피디아 / Java

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

 

• 인접한 두 개의 원소끼리 비교하여 정렬하는 방식

 

 

 

선택정렬 Selection Sort

출처 : 위키피디아 / Java

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

 

• 최소값을 찾아 선택해서 이동, 정렬하는 방식

 

 

 

 

삽입정렬 Insertion Sort

출처 : 위키피디아 / Java

void insertionSort(int[] arr)
{

   for(int index = 1 ; index < arr.length ; index++){

      int temp = arr[index];
      int aux = index - 1;

      while( (aux >= 0) && ( arr[aux] > temp ) ) {

         arr[aux+1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

 

• 두번째 인덱스부터 기준점을 잡고 시작한다.
• 기준점 앞에 있는 원소들만 비교해서 기준값을 이동시키는 정렬
• 기준점 앞 배열은 정렬이 되어있는 것이 특징이다. 

 

 

시간복잡도 비교 (빅오표기법 Big-O-Notation)

Name	Best	Avg	Worst	Run-time (정수 60,000개) (sec)
삽입정렬	n	n2	n2	7.438
선택정렬	n2	n2	n2	10.842
버블정렬	n2	n2	n2	22.894

• 단순하지만 비효율적.
• 복잡하지만 효율적인 정렬 알고리즘 -> 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬