버블 / 선택 / 삽입

 

 

 

 

버블 정렬

 

 

가장 기본적인 정렬 방법이다.

 

배열이나 리스트의 인덱스 0부터 시작해 오름차순으로 정렬을 수행한다.

 

import java.util.*;

public class BubbleSort {

    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
    
        for (int index = 0; index < dataList.size() - 1; index++) {
            boolean swap = false; // 정렬이 수행되지 않았다면 이미 정렬된 리스트이다. 
            
            for (int index2 = 0; index2 < dataList.size() - 1 - index; index2++) {
                if (dataList.get(index2) > dataList.get(index2 + 1)) {
                    Collections.swap(dataList, index2, index2 + 1);
                    swap = true;
                    // 이중 for문을 통해 오름차순으로 정렬한다.
                }
            }
            
            if (swap == false) {
                break;
            }
        }
        
        return dataList;
    }
}

 

시간복잡도 : O(n^2)

 

 

 

선택 정렬

 

 

 

배열이나 리스트의 인덱스 0부터 시작해 주어진 데이터에서 최솟값을 찾은 후 최솟값을 인덱스 i와 바꿔 줌으로 정렬한다.

 

import java.util*;

public class SelectionSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        int lowest;
        
        for (int stand = 0; stand < dataList.size() - 1; stand++) {
            lowest = stand;
            for (int index = stand + 1; index < dataList.size(); index++) {
                if (dataList.get(lowest) > dataList.get(index)) {
                    lowest = index;
                    
                }
            }
            Collections.swap(dataList, lowest, stand);
        }
        return dataList;
    }
}

 

시간복잡도 : O(n^2)

 

 

 

삽입 정렬

 

이중 반복문을 돌려 두 번째 반복문은 첫 번째 반복문의 변수보다 1큰 위치부터 접근해 앞의 원소와 비교해 값을 바꿔가며 정렬을 수행한다.

 

import java.util.*;

public class InsertionSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
    
        for (int index = 0; index < dataList.size() - 1; index++) {
            for (int index2 = index + 1; index2 > 0; index2--) {
                if (dataList.get(index2) < dataList.get(index2 - 1)) {
                    Collections.swap(dataList, index2, index2 - 1);
                } else {
                    break;
                }
            }
        }
        return dataList;
    }
}