• bubble sort

    • 인접한 데이터의 크기를 비교해 정렬하는 방법

    • O(n^2)

      • 루프 한 번 도는데 n번의 시간이 걸림(n번 돌면 1개 정렬

      • 근데 이걸 n번의 루프를 돈다고

        ⇒ n*n = n^2

    • 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬

    • 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이므로 프로세스 종료

    • 015 수 정렬하기 1

      • 1000개까지 수를 받을 수 있으므로 버블 정렬 쌉가능
      • sort() 함수 이용해도 되지만 정렬 직접 구현
      //버블 정렬
for(int i = 0; i < N-1; i++){//루프의 개수
	for(int j = 0; j < N-1-i; j++){//하나의 루프 개수에서 정렬하는 범위(아직 정렬되지 않은 배열의 영역)
		if(A[j] > A[j+1]){
			SWAP
			}
		}
	}

      • 왜 N-1-i 인가?

        루프를 한 번 돌 때마다 맨 끝에는 정렬이 되므로 하나의 루프를 돌고나면 아직 정렬되지 않은 범위가 1개씩 좁아지니까

    • 016 버블 소트 프로그램 1

      • N은 500,000보다 작거나 같은 수 이므로 N^2으로 절대 못풀고 NlogN으로 풀어야 함

      • swap이 일어나지 않음 = 이미 모든 데이터 정렬 완료

      • 버블 정렬의 이중 for문에서 내부 for문이 몇 번 수행됐는지는

        • 왼쪽에서 오른쪽으로 이동하며 swap을 수행하는데
        • 여기서 swap할 때 왼쪽으로 이동할 수 있는 최대 거리가 1임(인접한 두 수끼리 교환하는거니까)

        ⇒즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾고 거기에 1 더해주면 정답 출력

        **왜 1을 더해주는가?

        영식에가 작성한 코드를 보면 마지막에는 정렬이 다 완료되었기 때문에 swap이 일어나지 않음

        이 일어나지 않은 swap 반복문이 마지막에 1번 돌기 때문에 이 1번을 더해줘야 함

      • 왜 최대값을 구해야 하는가?

        • 예제 입력, 예제 출력을 보면 최대값이 나와야 함
        • 나는 영식이 코드로 보면 한 index의 값에서 swap이 일어날 때마다 count 값이 출력되어야 하는데 왜 출력값이 하나지? 라는 생각을 했는데
        • 문제 자체가 영식이 코드의 출력 값과 다름
        class Num implements Comparable<Num> {
    int value;
    int index;

    public Num(int value, int index) {
        this.value = value;
        this.index = index;
    }

    @Override
    public int compareTo(Num n) {
        System.out.println("비교: this.value = " + this.value + ", n.value = " + n.value);
        return this.value - n.value; // 오름차순 정렬
    }
}

public class Main {
    public static void main(String[] args) {
        Num[] A = {
            new Num(5, 0),
            new Num(2, 1),
            new Num(9, 2),
            new Num(3, 3)
        };

        Arrays.sort(A); // 정렬 실행
    }
}

      • Arrays.sort(A);가 정렬을 수행하면서 compareTo()를 계속 호출

      • compareTo()는 서로 다른 두 개의 객체를 비교할 때마다 실행

      • 정렬 알고리즘(Timsort)이 compareTo()의 결과(양수 or 음수)를 보고 자리 바꿈을 결정

        • 자바의 Arrays.sort(A);는 내부적으로 "Timsort" 라는 정렬 알고리즘을 사용
        • 정렬 과정에서 서로 다른 두 개의 객체를 계속 비교하면서 compareTo()를 호출

      **

      • this는 현재 비교의 기준이 되는 객체
      • n은 비교 대상으로 넘겨진 객체
      • 정렬 과정에서 this와 n은 계속 바뀌면서 여러 번 비교가 이루어짐
      • this.value - n.value가 양수면 자리 바꿈, 음수면 유지됨

      **

  • selection sort

    • 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법
    • O(n^2)
      • 선택 정렬은 마지막 최대값이 fix가 되는데
      • 1개를 fix하는데 n만큼의 탐색이 필요함
      • 그럼, n개를 fix하려면 n만큼의 탐색이 필요함 ⇒ n*n = n^2
    • 정렬해야 하는 부분에서 최소 또는 최댓값을 찾음
    • 정렬해야 하는 부분에서 가장 앞에 있는 데이터와 선택된 데이터 swap
    • 위치 변경 후 정렬해야 하는 부분의 범위 축소함
    • 017 내림차순으로 자릿수 정렬하기
      • N이 1,000,000,000보다 작거나 같은 수이지만 이 경우엔 자릿수 문제이므로 1,000,000,000이라고 한들 자릿수는 10임 따라서 어떤 알고리즘 써도 상관없음
      • 숫자를 각 자릿수별로 나누는 작업이 필요
        • String 값으로 N값을 받아 SubString()으로 int 배열에 저장

  • insert sort

    • 이미 정렬된 데이터 범위에서 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식

    • O(n^2)

    • 현재 index에 있는 데이터 값 선택

    • 현재 선탣한 데이터가 정렬된 데이터 범위에 삽입될 위치 탐색

    • 삽입 위치부터 index에 있는 위치까지 shift 연산 수행

    • 삽입 위치에 현재 선탣한 데이터 삽입한 후 index++ 수행

      image.png

    • 018 ATM 인출 시간 계산하기

      • ATM 앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서 정하기 → 그리디 방식
      • 즉, 인출 시간을 기준으로 값 정렬(오름차순 정렬)
      • 정렬된 데이터(오름차순) 바탕으로 합 배열
        • 앞사람들의 인출 시간의 합 + 자신의 인출 시간이므로 합 배열 이용
      import java.util.Scanner;

public class P11399 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int A[] = new int[N];
		int S[] = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		
		//삽입 정렬
		for(int i = 1; i < N; i++) {
			int insert_point = i;//현재 index
			int insert_value = A[i];//현재 데이터
			
			for(int j = i - 1; j >= 0; j--) {//뒤어서부터 검색
				if(A[j] < A[i]) {//나(A[i])보다 작은 값이 나타나면
					//현재 범위에서 삽입 위치 찾기
					insert_point = j + 1;
					//A[i]가 A[j] 바로 다음 자리에 삽입되어야 하니까
					//A[i]가 A[j+1]자리에 삽입되어야 함
					break;
				}
				if (j==0) {//끝까지 탐색완료
					//즉, 삽입될 위치가 가장 작은 값임을 뜻 함
					insert_point = 0;
				}					
			}
			
			//삽입을 위해 삽입 위치에서 i까지 데이터 한 칸씩 뒤로 밀기
			for(int j =i; j > insert_point; j--) {
				A[j] = A[j-1]; //왜 A[j-1]냐고
				/*
				 A[1] = A[0]
				 A[2] = A[1]
				 보면 배열에 첫번째 요소가 그 다음 두번째 요소로 들어감
				 그니까 뒤로 한개씩 밀리는거임
				 * 
				 */
			}
			//삽입 위치에 현재 데이터 삽입
			A[insert_point] = insert_value;
		}
		
		//합배열
		S[0] = A[0];
		for(int i = 1; i < N; i++) {
			S[i] = S[i-1] + A[i];
		}
		
		//총합 구하기
		int sum = 0;
		for(int i = 0; i < N; i++) {
			sum = sum + S[i];
		}
		System.out.println(sum);
	}

}

  • quick sort

    • pivot 선정해서 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘

    • pivot이 어떻게 선정되는지에 따라 시간복잡도가 O(nlogn) 또는 O(n^2)이 나옴

      **평균은 O(nlogn)임

    • 과정

      • pivot 설정(가장 오른쪽 끝을 pivot으로 설정)
      • pivot 기준으로 2개의 집합으로 분리
      • start가 가리키는 데이터가 pivot 보다 작으면 start를 오른쪽으로 한 칸 이동
      • end가 가리키는 데이터가 pivot 보다 크면 end를 왼쪽으로 한 칸 이동
      • start가 가리키는 데이터가 pivot 보다 크고 end가 가리키는 데이터가 pivot 보다 작으면 start ↔ end swap한 후, start는 오른쪽, end는왼쪽으로 1칸 이동
      • start와 end가 만나면 그 가리키는 데이터와 pivot을 비교하여 pivot보다 크면 만난 지점의 오른쪽에 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터 삽입
      • 분리 집합에서 각각 다시 pivot 선정
      • 분리 집합이 1개가 될 때까지 위 과정 반복

    • 019 k번째 수 구하기

      • 500만까지입력할 수 있으므로 N^2은 불가능함

      • 퀵정렬인 O(nlogn)으로 풀어야 함

      • pivot은 중앙값으로 설정하여 풀이

        • pivot == k: k번째 수를 출력하는 것이 답이므로 k값을 찾았기 때문에 바로 알고리즘 종료
        • pivot > k : pivot의 왼쪽 부분에 k가 있으므로 왼쪽부분만(s~pivot-1) 정렬 수행
        • pivot < k : pivot의 오른쪽 부분에 k가 있으므로 오른쪽부분만(pivot+1~e) 정렬 수행

      • 중간 위치를 pivot으로 설정한 후 맨 앞에 값과 swap함

        ⇒왜? i, j 이동을 편하게 하기 위함(그럼 i는 index 1번, j는 마지막 index인 것)

      • 우선 j를 이동함 pivot < A[j]라면 j-- 연산 반복

      • j 이동 후 i < pivot && i < j 라면 i++ 반복

      • i == j 라면 A[i] ← swap → A[j]

  • merge sort

  • radix sort