[이것이 코딩 테스트다 with Java] 정렬 (Sort)

정렬(Sort)

 

개요

데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램 작성 시에 가장 많이 사용되는 알고리즘 중 하나이다. 예를 들어 이진 탐색을 하기 위해서는 전처리 과정으로 정렬이 필요하다.

 

선택정렬

데이터가 무작위로 여러 개 있을 때 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 방식이다. 가장 원식적인 방법으로 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다. 선택 정렬의 시간 복잡도는 O(N²)이다. 소스코드는 다음과 같다.

import java.util.*;

public class Main
{
	public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        
        // 선택정렬 구현
        for(int i = 0; i < arr.length - 1; i++){
            // 가장 작은 원소의 Idx
            int minIdx = i;
            
            for(int j = i + 1; j < arr.length; j++){
                if(arr[minIdx] > arr[j]){
                    minIdx = j;
                }
            }
            
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
        
        for(int num : arr){
            System.out.print(num + " ");    
        }
	}
}

 

삽입 정렬

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입된다는 점이 특징이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 삽입 정렬의 시간 복잡도는 최악의 경우 O(N²), 최선의 경우 O(N)이다. 소스코드는 다음과 같다. 

public class Main
{
	public static void main(String[] args) {
		  int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
		  
		  for(int i = 1; i < arr.length; i++){
		      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 num : arr){
            System.out.print(num + " ");
		  }
	}
}

 

퀵 정렬

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 이때 기준이 되는 수를 퀵 정렬에서 피벗(pivot)이라고 한다. 대표적인 분할 방식으로는 리스트에서 첫 번째 데이터를 피벗으로 정하는 호어 분할 방식이 있다. 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 다만 데이터가 무작위로 입력되는 경우 빠르게 동작할 확률이 높은 퀵 정렬은 이미 데이터가 정렬되어 있는 최악의 경우 O(N²)이라는 시간 복잡도를 가진다. 소스코드는 다음과 같다.

public class Main
{
	public static void main(String[] args) {
		  int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
		  
		  quickSort(arr, 0, arr.length-1);
		  
		  for(int num : arr){
		    System.out.print(num + " ");
		  }
	}
	
	public static void quickSort(int[] arr, int start, int finish){
	    if(start >= finish){
	        return ; 
	    }
	    
	    int pivot = start;
	    int left = start + 1; 
	    int right = finish;
	    
	    while(left <= right){
	        // 피벗보다 큰 데이터를 찾을 때까지 반복
	        while(left <= finish && arr[left] <= arr[pivot]) left++;
	        // 피벗보다 작은 데이터를 찾을 때까지 반복
	        while(right > start && arr[right] >= arr[pivot]) right--;
	        
	        int temp = arr[right];
	        
	        if(left > right){
	            arr[right] = arr[pivot];
	            arr[pivot] = temp;
	        }else{
	            arr[right] = arr[left];
	            arr[left] = temp;
	        }
	    }
	    
	    quickSort(arr, start, right -1);
	    quickSort(arr, right + 1, finish);
	}
}

 

계수 정렬

데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있는 매우 빠른 정렬 알고리즘이다. 일반적으로 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식이 아니며 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 계수 정렬의 시간 복잡도는 O(N + K)이다. 여기서 N은 데이터의 개수, K는 데이터 중 최댓값을 의미한다. 소스코드는 다음과 같다.

public class Main
{
    public static final int MAX_VALUE = 9;
    
	public static void main(String[] args) {
	    int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
		  
		int count[] = new int[MAX_VALUE+1];
		  
		for(int num : arr){
		    count[num]++;
		}
		
		for(int i = 0; i < count.length; i++){
		    System.out.print((i + " ").repeat(count[i]));
		}
		
	}
}

 

예제 1 - 위에서 아래로

난이도 ●○○ | 풀이 시간 15분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 T 기업 코딩 테스트

하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관없이 무작위로 주어진다. 이 수를 큰 수부터 작은 수까지 내림차순으로 정렬하면 되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면 된다.

 

입력 조건

• 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1 <= N <= 500
• 둘째 줄부터 N + 1 번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하 자연수

 

출력 조건

• 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분해서 출력하면 된다. 동일한 수는 순서 상관없다.

 

입력/출력 예시

입력 예시	출력 예시
3 15 27 12	27 15 12

 

요점

• 입력 가능한 수열의 최대 개수가 500이므로 어떤 정렬 알고리즘을 사용해도 문제없음
• 간단한 정렬 문제이기 때문에 사용 언어에서 제공하는 기본 정렬 알고리즘을 사용하는 것이 효율적

 

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		Integer numbers[] = new Integer[n];
		
		for(int i = 0; i < n; i++){
		    numbers[i] = scan.nextInt();
		}
		
		Arrays.sort(numbers, Comparator.reverseOrder());
		
		for(int number : numbers){
		    System.out.print(number + " ");
		}
		
	}
}

 

예제 2 - 성적이 낮은 순서대로 학생 출력하기

난이도 ●○○ | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 D 기업 프로그래밍 콘테스트 예선

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

 

입력 조건

• 첫 번째 줄에 학생의 수 N이 입력된다. (1 ≤ N ≤ 100,000)
• 두 번째 줄부터 N + 1 번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

 

출력 조건

• 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

 

입력/출력 예시

입력 예시	출력 예시
2  홍길동 95  이순신 77	이순신 홍길동

 

요점

• 출력 시에는 학생 이름만 출력하면 되므로 학생 정보를 (점수, 이름)으로 묶은 뒤에 점수를 기준으로 정렬을 수행

 

소스 코드

import java.util.*;

// 학생 클래스
class Student{
    String name; 
    int score;
    
    public Student(String name, int score){
        this.name = name;
        this.score = score;
    }
    
    public String getName(){
        return this.name;
    }
    
    public int getScore(){
        return this.score;
    }
}


public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();

        List<Student> students = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String name = scan.next();
            int score = scan.nextInt();
            students.add(new Student(name, score));
        }
        
        // 정렬 후 출력
        students.stream().sorted(Comparator.comparing(Student::getScore))
                         .forEach(s -> System.out.print(s.getName() + " "));
        

	}
}

 

예제 3 - 두 배열의 원소 교체

난이도 ●○○ | 풀이 시간 20분 | 시간 제한 2초 | 메모리 제한 128MB | 기출 국제 알고리즘 대회

빈이는 두 개의 배열 A와 배열 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.

N, K 그리고 배열 A와 배열 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

 

입력 조건

• 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1 <=N <=100,000 , 0 <=K <=N)
• 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
• 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 자은 자연수입니다.

 

출력 조건

• 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
5 3  1 2 5 4 3  5 5 6 6 5	26

 

요점

• 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체
• 배열 A와 배열 B의 정보가 입력되면 배열 A의 원소를 오름차순으로 정렬하고, 배열 B의 원소를 내림차순으로 정렬
• 그 후 두 배열의 원소를 가장 첫 번째 인덱스부터 차례대로 비교

 

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);

	    int n = scan.nextInt();
	    int k = scan.nextInt();

	    Integer arrA[] = new Integer[n];
	    Integer arrB[] = new Integer[n];

	    for (int i = 0; i < n; i++) {
	        arrA[i] = scan.nextInt();
	    }
        
	    for (int i = 0; i < n; i++) {
	        arrB[i] = scan.nextInt();
	    }
        
	    Arrays.sort(arrA); // 오름차순 정렬
	    Arrays.sort(arrB, Comparator.reverseOrder()); // 내림차순 정렬
        
	    for(int i = 0; i < k; i++){
	        if(arrA[i] >= arrB[i]) break;
	        
	        int temp = arrA[i];
	        arrA[i] = arrB[i];
	        arrB[i] = temp;
	    }
        
	    long result = Arrays.stream(arrA).mapToInt(i -> i).sum();
        
	    System.out.println("result = " + result);
	}
}

 

정렬 예제를 풀어본 후

정렬은 다양한 방법이 있는 만큼 하고자 하면 어떻게든 수행할 수 있지만 데이터의 특성과 크기에 맞게 적절한 알고리즘을 선택한다는 건 어려운 것 같다. 또한 그게 알고리즘을 공부해야 하는 이유라고 생각한다. 정렬 알고리즘을 공부할 때는 단순히 동작 방식을 이해하는데 그치지 않고 각 알고리즘의 특성과 시간 복잡도 등도 함께 이해하고 있다면 더 좋을 것 같다. 물론 실제론 각 언어에서 제공하는 정렬 라이브러리를 주로 사용하긴 해도 아는 것은 힘이니까..!

 

 

GitHub: https://github.com/Leeyeonjae/coding-test/tree/main/6_Sort

참고서적 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈