[Java 정렬] Bubble Sort(버블 정렬), Insertion Sort(삽입 정렬), Selection Sort(선택 정렬)

정렬?

---

정렬은 특정 값을 기준으로 순서대로 데이터를 배치하는 방법을 말한다.

구현 난이도가 쉽고 속도가 느린 정렬로는 버블정렬, 삽입정렬, 선택정렬.

 구현 난이도가 좀 더 어렵고 속도가 빠른 정렬로는 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬.

 하이브리드 정렬로는 팀 정렬, 블록 병합 정렬, 인트로 정렬.

 기타 정렬 알고리즘으로는 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬 등이 있다.

 

 

Bubble Sort(버블 정렬)

---

인접한 데이터를 비교하여 자리를 바꾸는 방식으로 알고리즘 복잡도는 O(n제곱) 이다.

 

 

 

 for (int i = 1; i < arr.length - 1; i++) { 
            for (int j = 0; j < arr.length - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }

        }

     for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[ j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }

        }

 

이런 식으로 사용이 가능하다.

 

 

Insertion Sort(삽입 정렬)

---

앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식으로, 알고리즘 복잡도는 O(n제곱)이다.

 

 for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if(arr[j] < arr[j-1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                }else{  //앞의 데이터들이 이미 정렬이 되있어서 비교할 필요가 없음.
                    break;
                }
            }
        }

 

 

 

Selection Sort(선택 정렬)

---

최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식으로, 알고리즘 복잡도는 O(n제곱)이다.

 

      //최소값
        for (int i = 0; i < arr.length-1; i++) {  
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[min]) {
                    min = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }

        //최대값
        for (int i = arr.length -1; i >0 ; i--) {
            int max = i;
            for (int j = i-1; j >=0; j--) {
                if(arr[j] > arr[max]) {
                   max = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[max];
            arr[max] = tmp;
        }