정렬

• 정렬이랑 데이터를 특정한 기준에 따라 순서대로 나열하는 것

 

• 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것

처리되지 않은 데이터 중 가장 작은 '0'을 선택해 가장 앞의 '7'과 바꿈

처리되지 않은 데이터 중 가장 작은 '2'를 선택해 가장 앞의 '9'와 바꿈

이러한 일련의 과정을 반복하면 정렬이 완료됨

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        
        for(int i=0;i<n;i++) {
        	int min_index = i; //가장 작은 원소의 인덱스
            for(int j=i+1; j<n; j++) {
            	min_index = j;
            }
        }
        //스와프
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
   	 }
   		for(int i=0;i<n;i++) {
        	System.out.print(arr[i]+" ");
    	}
    }
}

• 시간 복잡도는 O(N의 2제곱)

 

• 삽입 정렬 : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 방법

첫번째 데이터 '7'은 그 자체로 정렬이 되어있다고 판단하고, 두번째 데이터 '5'가 어떤 위치로 들어갈지 판단. 오름차순일 경우 '5'의 값이 더 작으면 왼쪽

이어서 '9'가 어떤 위치로 들어갈지 판단

import java.util.*;

public calss Main {
	public static void main(String[] args) {
    	int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        for(int i=1;i<n;i++) {
       		//인덱스 i부터 1까지 감소하며 반복하는 문법
        	for(int j=i;j>0;j--) {
            	//한 칸씩 왼쪽으로 이동
                if(arr[j] < arr[j-1]) {
                	//스와프
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                //자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                else break;
            }
        }
        for(int i=0;i<n;i++) {
        	System.out.print(arr[i]+" ");
        }
    }
}

• 시간복잡도는 O(N의 제곱)
• 현재 리스트의 데이터가 거의 정렬되어 있는 상태는 매우 빠르게 동작하므로 최선의 경우 O(N)의 시간 복잡도 가짐