[Algorithm] 정렬(Sorting)

안녕하세요. J4J입니다.

 

이번 포스팅은 정렬 알고리즘에 대해 적어보는 시간을 가져보려고 합니다.

 

 

정렬 알고리즘이란?

 

정렬 알고리즘은 배열 등에 저장되어 있는 요소들을 일정한 순서대로 정렬(재 배치) 하는 것을 의미합니다.

 

예를 들어 배열에 저장되어 있는 정수 값들을 크기가 작은 순서대로 정렬할 때 사용되거나(오름차순 이라고도 하죠) 또는 알파벳으로 이루어진 문자열들을 사전 순서대로 정렬할 때 사용될 수 있습니다.

 

정렬 알고리즘 종류에는 선택 정렬(selection sort), 삽입 정렬(insertion sort), 퀵 정렬(quick sort), 합병 정렬(merge sort) 외에도 많은 종류들이 존재합니다.

 

이런 정렬 들 중 퀵 정렬이 가장 흔하게 사용되고는 하는데 그 이유는 정렬을 할 때 가장 효율적인 방법으로 정렬이 되기 때문입니다. (퀵 정렬이 정렬할 때 사용되는 시간이 가장 짧은 편입니다.)

 

각각의 정렬들을 구현하는 것은 추후 포스팅을 하도록 하고 이번 포스팅에는 자바에서 제공해주는 정렬 메서드들에 대해 소개해보도록 하겠습니다.

 

 

자바 정렬 메서드

 

자바에서 제공해주는 정렬 메서드는 대표적으로 배열과 컬렉션에 대한 정렬 메서드를 제공해주고 있습니다.

 ※ 컬렉션에 대해 모르신다면? [Java] 자바기초 - 컬렉션(Collection)

 

배열에 대한 정렬은 java.util.Arrays에 정의되어 있고 컬렉션에 대한 정렬은 java.util.Collections에 정의되어 있습니다.

 

Arrays 같은 경우는 이중 퀵 정렬을 사용하여 정의되어 있는데 기존의 퀵 정렬의 단점을 보완한 정렬이라고 생각하시면 됩니다. (퀵 정렬의 단점은 정렬 상태일 때 사용하면 시간이 오래 걸린다는 겁니다.)

 

Collections 같은 경우는 합병 정렬을 사용하여 정의되어 있습니다.

 

 

자바 메서드 사용 방법

 

Arrays와 Collections 모두 sort()라는 메서드에 정렬코드가 구현되어 있고 Arrays.sort(), Collections.sort()의 형태로 사용할 수 있습니다.

 

그리고 해당 메서드는 오버로딩되어 작성되었기 때문에 두 가지 사용법에 대해 말씀드리겠습니다.

 ※ 오버로딩에 대해 모르신다면? [Java] 자바기초 - 오버라이딩과 오버로딩(overriding/overloading)

 

첫 번째는 sort(T[] a)의 형태입니다.

 

이 형태는 사용자가 원하는 정렬대로 적용시켜주지 못하고 단순히 오름차순의 형태로 정렬이 됩니다.

 

두 번째는 sort(T[] a, Comparator<? super T> c)의 형태입니다.

 

이 형태는 첫 번째 케이스와 달리 Comparator라는 익명 클래스를 사용하여 정렬해주는 방식이고 사용자가 원하는 정렬방식으로 구현할 수 있습니다.

 

Arrays 메서드들을 사용하여 코드를 작성해보겠습니다.

 

package sorting;

import java.util.Arrays;
import java.util.Comparator;

public class ArraySort {
	public static void main(String[] args) {
		int[] intArray = new int[]{3, 7, 2, 14, 13, 5};
		String[] stringArray = new String[]{"abc", "cde", "qq", "dd", "aacx", "aqq", "ab"};
		
		Arrays.sort(intArray); // 첫 번째 방식, 오름차순 정렬
		Arrays.sort(stringArray, new Comparator<String>() { // 두 번째 방식
			@Override
			public int compare(String o1, String o2) { // 내림차순 정렬 (사전식의 반대)
				return o2.compareTo(o1); // compareTo는 문자열 비교 메서드
			}
		});
		
		System.out.println(Arrays.toString(intArray)); // [2, 3, 5, 7, 13, 14]
		System.out.println(Arrays.toString(stringArray)); // [qq, dd, cde, aqq, abc, ab, aacx]
	}
}

 

 

위의 코드처럼 Comparator을 사용하지 않는 sort()는 오름차순으로 정렬 해주지만 Comparator을 사용하는 sort()에서는 정렬될 배열의 타입을 제네릭으로 사용한 new Comparator라는 익명 클래스에 compare라는 메서드를 추가적으로 작성하여 사용자가 원하는 방식으로 정렬해줄 수 있습니다.

 

 

728x90

 

 

지금은 Comparator을 사용한 sort()를 내림차순으로 정렬했지만 return 값을 o1.compareTo(o2)라고 변경하면 오름차순으로 정렬됩니다. (정수값이나 실수값일 경우는 return o1 - o2이면 오름차순, return o2 - o1이면 내림차순)

 

Collections도 다음 코드와 같이 Arrays와 동일하게 작성하여 사용할 수 있습니다.

 

package sorting;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CollectionsSort {
	public static void main(String[] args) {
		List<Integer> intList = new ArrayList<Integer>();
		intList.add(3);
		intList.add(7);
		intList.add(2);
		intList.add(14);
		intList.add(13);
		intList.add(5);
		
		List<String> stringList = new ArrayList<String>();
		stringList.add("abc");
		stringList.add("cde");
		stringList.add("qq");
		stringList.add("dd");
		stringList.add("aacx");
		stringList.add("aqq");
		stringList.add("ab");
		
		Collections.sort(intList); // 첫 번째 방식, 오름차순 정렬
		Collections.sort(stringList, new Comparator<String>() { // 두 번째 방식
			@Override
			public int compare(String o1, String o2) { // 내림차순 정렬 (사전식의 반대)
				return o2.compareTo(o1); // compareTo는 문자열 비교 메서드
			}
		});
		
		System.out.println(intList); // [2, 3, 5, 7, 13, 14]
		System.out.println(stringList); // [qq, dd, cde, aqq, abc, ab, aacx]
	}
}

 

 

추가적으로 제네릭에 자료형의 Wrapper클래스가 아닌 클래스 값을 집어넣을 경우도 코드로 작성해보겠습니다.

 ※ Wrapper Class에 대해 모르신다면? [Java] 자바기초 - Wrapper Class

 

package sorting;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ClassSort {
	public static void main(String[] args) {
		List<Node> nodeList = new ArrayList<Node>();
		
		nodeList.add(new Node(0, "qqw"));
		nodeList.add(new Node(5, "aaasd"));
		nodeList.add(new Node(2, "wqexx"));
		nodeList.add(new Node(8, "zzzzzz"));
		nodeList.add(new Node(4, "zzzzzz"));
		nodeList.add(new Node(3, "pppo"));
		
		Collections.sort(nodeList); // 첫 번째 방식, Error
		Collections.sort(nodeList, new Comparator<Node>() { // 두 번째 방식
			@Override
			public int compare(Node o1, Node o2) { // Node의 stringVal이 동일하다면 index로 내림차순, 동일하지 않다면 stringVal로 내림차순
				return o2.stringVal.compareTo(o1.stringVal) == 0 ? o2.index - o1.index : o2.stringVal.compareTo(o1.stringVal);
			}
		});
		
		System.out.println(nodeList); // [
        						 // 	Node [index=8, stringVal=zzzzzz],
        						 //	Node [index=4, stringVal=zzzzzz],
        						 // 	Node [index=2, stringVal=wqexx], 
        						 // 	Node [index=0, stringVal=qqw], 
        						 // 	Node [index=3, stringVal=pppo], 
        						 // 	Node [index=5, stringVal=aaasd]
        						 // ]
	}
	
	private static class Node {
		int index;
		String stringVal;
		
		public Node(int index, String stringVal) {
			this.index = index;
			this.stringVal = stringVal;
		}

		@Override
		public String toString() { // 출력을 위해 오버라이딩
			return "Node [index=" + index + ", stringVal=" + stringVal + "]";
		}
	}
}

 

 

위의 코드와 같이 첫 번째 sort() 방식은 오름차순을 위한 변수 타입을 정할 수 없기 때문에 에러가 발생합니다.

 

그리고 두 번째 sort() 방식은 위의 코드처럼 Node 클래스 내부의 한 가지 변수에 대한 것이 아닌 여러 변수에 대한 정렬도 작성할 수 있습니다.

 

return에 작성한 코드를 간단히 설명을 해드리자면 먼저 stringVal로 내림차순하고 내림차순된 형태를 다시 index로 내림차순 해주는 겁니다.

 

그렇기 때문에 가장 먼저 stringVal에 대한 내림차순을 적용시키기 위해 stringVal값을 서로 비교합니다.

 

compareTo 메서드의 결과값이 0일 경우는 stringVal의 값이 동일하기 때문에 index들의 크기를 리턴하고 stringVal의 값이 동일하지 않을 경우는 compareTo 메서드의 결과값을 리턴해주는 겁니다.

 

 

정리

 

● 정렬(Sorting)은 요소들을 일정한 순서대로 정렬 및 재 배치를 하기 위해 사용

● 자바에서는 배열과 컬렉션에 대한 Arrays.sort()와 Collections.sort()를 제공

 

 

 

이상으로 정렬에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.