[BOJ] 백준 2750 수 정렬하기

출처: https://www.acmicpc.net/problem/2750

삽입 정렬을 이용해 구현

- 배열 index에 적절한  값을 찾아갑니다.

array = { 1, x, 5, 7, 2 }

    1 < 2   

    2 < 5 "stop"

array = { 1, 3, x, 8, 9, 7 }

    1 < 7 

    3 < 7   

    7 < 8 "stop"

 

퀵 정렬 이용한 C 소스

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int arr[1000];
 
int swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void quickSort(int start, int end) {
    if (start >= end) return;
    int pivot = start, left = start + 1, right = end;
    while (1) {
        while (left <= end && arr[left] <= arr[pivot]) left++;
        while (right > start && arr[right] >= arr[pivot]) right--;
        if (left > right) {
            swap(&arr[pivot], &arr[right]);
            break;
        }
        else swap(&arr[left], &arr[right]);
    }
    quickSort(start, right - 1);
    quickSort(right + 1, end);
}
 
int main(void) {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    quickSort(0, N - 1);
    for (int i = 0; i < N; i++) {
        printf("%d\n", arr[i]);
    }
    return 0;
}

---

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.nextLine());
         
        int[] arr = new int[N];
         
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(sc.nextLine());
        }
         
        insertSort(arr);
         
        for(int i=0; i<N; i++) {
            System.out.println(arr[i]);
        }
    }
 
    private static void insertSort(int[] arr) {
        // 2번째 원소부터
        for(int i=1; i<arr.length; i++) {    
             
            // 탐색하는 원소의 앞 원소들로만 비교
            for(int j=0; j<i; j++) {
                if(arr[i] < arr[j]) {
                    // 자리를 바꿔야 된다면
                    // 해당 원소는 앞으로 이동하고
                    // 나머지 원소들은 뒤로 이동되듯이 swap
                    for(int k=i; k>j; k--) {
                        swap(arr,k,k-1);
                    }
                    // 현재 해당 원소에 대해서 제위치를 찾아갔으므로 다음 단계로
                    break;
                }
            }
        }
    }
 
    private static void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}