bubble sort, selection sort, insertion sort

bubble sort

---

bubble sort(버블 정렬)란 매번 연속된 두 개의 인덱스를 비교하여 정렬하는 방법이다.

 

• 버블 정렬은 첫 번째 인덱스(기준 인덱스)부터 시작
• 기준 인덱스 뒤에 있는 데이터와 비교하여 뒤에 있는 데이터가 크면 자리를 교체함
• 기준 인덱스를 한 칸 뒤 인덱스로 이동시켜 다시 비교를 진행하고 해당 과정을 마지막 인덱스 비교까지 반복함

※ 과정을 반복할 때마다 가장 마지막에 위치하는 인덱스 값이 비교하는 값들 중에서 가장 큰 값이 위치하게 되므로 매 수열 비교 시마다 가장 마지막 수를 제외하고 진행을 하게 된다. 

노란색 = 비교, 파랑색 = 교체, 회색 = 확정

 

위와 같은 과정을 정렬이 완료될 때까지 진행을 하게 되면 정렬된 1, 2, 3, 4, 7의 정렬된 값을 가진 ArrayList가 결과로 나오게 된다. 아래 그림은 bubble sort의 모든 과정을 표현한 그림이다.

 

 

bubble sort 구현해 보기

---

public ArrayList<Integer> bubbleSort(ArrayList<Integer> bubbleArr) {
        
        for(int i = 0 ; i < bubbleArr.size() - 1 ; i++) {
            //교체가 한번이라도 이루어졌는지 확인하기 위한 flag
            boolean swapFlag = false;
            for(int j = 0 ; j < bubbleArr.size() - 1 - i ; j++) {
                //마지막 인덱스는 비교대상에서 제외 되므로 bubbleArr.size() - 1 - i까지 for문을 진행시킨다.
                if(bubbleArr.get(j) > bubbleArr.get(j+1)) {
                    Collections.swap(bubbleArr, j, j+1);
                    swapFlag = true;
                }
            }

            //한번도 교체가 이루어 지지 않았다는 것은 이미 정렬이 되어 있다는 뜻이므로 비교를 종료한다.
            if(!swapFlag) {
                break;
            }
        }

        return bubbleArr;
    }

 

selection sort

---

selection sort(선택 정렬)란 수열을 선형 탐색하여 해당 수열 중에서 가장 작은 값을 찾아 앞쪽으로 이동하기를 정렬이 완료될 때까지 진행하는 방법이다.

• 주어진 데이터 중, 최솟값을 찾음
• 해당 최솟값을 데이터 맨 앞에 위치한 값과 교체함
• 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

파랑색 = 최솟값, 노란색 = 비교대상, 회색 = 확정

위와 같은 과정을 정렬이 완료될 때까지 진행을 하게 되면 정렬된 1, 2, 3, 4, 7의 정렬된 값을 가진 ArrayList가 결과로 나오게 된다. 아래 그림은 selection sort의 모든 과정을 표현한 그림이다.

 

 

selection sort 구현해보기

---

public ArrayList<Integer> selectionSort(ArrayList<Integer> selectionArr) {
        for(int i = 0 ; i < selectionArr.size() - 1 ; i++) {
            //최솟값 지정
            int min = i;
            for(int j = i + 1 ; j < selectionArr.size() ; j++) {
                if(selectionArr.get(j) < selectionArr.get(min)) {
                    //지정된 최솟값보다 더 작은 값인 경우
                    min = j;
                }
            }
            Collections.swap(selectionArr, i, min);
        }

        return selectionArr;
    }

 

insertion sort

---

insertion sort(삽입 정렬)란 정렬이 되어있지 않은 부분의 데이터를 뽑아서 정렬된 부분의 적절한 위치에 삽입하는 방법이다. 즉, 자료 배열의 모든 요소를 앞에서부터  차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성시킨다. 

 

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날 때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

위와 같은 과정을 정렬이 완료될 때까지 진행을 하게 되면 정렬된 1, 2, 3, 4, 7의 정렬된 값을 가진 ArrayList가 결과로 나오게 된다. 아래 그림은 insertion sort의 모든 과정을 표현한 그림이다.

노란색 = 비교, 파랑색 = 교체

 

insertion sort

---

public ArrayList<Integer> insertionSort(ArrayList<Integer> insertionArr) {

        for (int i = 0 ; i < insertionArr.size() - 1 ; i++) {
            for (int j = i + 1 ; j > 0 ; j--) {
                if(insertionArr.get(j) < insertionArr.get(j - 1)) {
                    Collections.swap(insertionArr, j, j - 1);
                } else {
                    break;
                }
            }
        }

        return insertionArr;
    }