[개념] 정렬 알고리즘

1. 배열 정렬하기 위한 내장 메서드(java.util.Arrays)

 

1) Arrays.sort(Array) : 기본 유형 또는 객체의 배열을 오름차순으로 정렬

2) Arrays.sort(Array, fromIndex, toIndex) : fromIndex 및 toIndex 매개변수로 지정된 배열의 일부만 정렬

3) Arrays.sort(Array, comparator) : Comparator를 사용하여 배열 정렬

4) Arrays.parallelSort(Array) : 여러 스레드를 활용하여 배열 병렬로 정렬

5) Arrays.parallelSort(Array, fromIndex, toIndex) : 오버로드된 parallelSort 메서드 버전을 사용하여 배열의 특정 요소 범위를 정렬

 

import java.util.Arrays;

public class StringSortExample {
    public static void main(String[] args) {
        //문자열 오름차순 정렬
        String[] arr = {"aa", "ee", "cc", "bb"};

        Arrays.sort(arr);
        for (String s : arr) {
            System.out.println(s);
        }
        
        //정수형 오름차순 정렬
        int[] numbers1 = {8, 2, 7, 3, 1, 5};
        
        Arrays.sort(numbers);
        for (int number : numbers1) {
            System.out.println(number);
        }
        
        //내림차순 정렬
        Integer[] numbers2 = {8, 2, 7, 3, 1, 5};

        Arrays.sort(numbers, Comparator.reverseOrder());
        for (int number : numbers2) {
            System.out.println(number);
        }
    }
}

 

2. java로 자체 작성된 정렬 알고리즘

 

1) 버블 정렬(Bubble Sort): 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

 > 간단하게 구현할 순 있지만 시간복잡도는 다른 정렬 알고리즘보다 속도가 느린 편이다.

2) 선택 정렬(Selection Sort): 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하며 정렬하는 방식

> 대상 데이터에서 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법으로 구현 방법이 복잡하고 시간 복잡도도 효율적이지 않다.

3) 삽입 정렬(Insertion Sort): 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식

 > 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식으로 시간복잡도는 느린편이지만 구현하지 쉽다. 

*적절한 삽입 위치를 탐색하는 부분에서 이진탐색(binary search) 등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.

4) 퀵 정렬(Quick Sort): pivot값을 선정해 해당 값을 기준으로 정렬하는 방식

> 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘으로 기준값이 어떻게 선정되는지가 시간복잡도에 많은 영향을 미친다.

5) 병합 정렬(Merge Sort): 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식

6) 기수 정렬(Radix Sort): 데이터의 자릿수를 바당으로 비교해 데이터를 정렬하는 방식

 

int n = 5;
int[n] arr = {1,2,3,4,5};

//버블정렬
for(int i=0;i<n-1;i++){
	for(int j=0;j<n-1-i;j++){
    	if(arr[j]>arr[j+1]){
        	int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

//선택정렬
for(int i=0; i<n; i++){
	int max = 1;
	for(int j=i+1; j<n; j++){
		if(arr[j]>a[max]){
			max = j;
		}
	}
	if(arr[i] < a[max]){
		int temp = arr[i];
		arr[i] = arr[max];
		arr[max] = temp;
	}
}

//삽입정렬
public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }
}

//퀵정렬
public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

}

//병합정렬
public class MergeSort {
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }
}

 

 

 

 

[출처: https://codegym.cc/ko/groups/posts/ko.1107.java---]