Quicksort(4) : System Sorts

Sorting applications

 

 

 

Java system sorts

자바에도 정렬 함수가 내장되어 있습니다(파이썬도 당연히..! 심지어 성능도 좋아요).

quick/merge sort 두 종류가 포함되어 있는데, 객체의 종류에 따라 다른 정렬을 사용한다고 합니다.

• 예를 들어 reference type에는 merge sort가 사용됩니다.
• 반대로 메모리가 적게 필요하고 in-place 변화가 적용되는 경우에는 quick sort가 사용됩니다.

 

 

War story (C qsort function)

 

 

 

Enginerring a system sort

 

 

 

Tukey's ninther

중간값의 중간값을 고르는 방법을 제안한 학자입니다.

이 방식은 랜덤하게 값을 섞는것보다 구분 효과가 탁월하고 비용은 덜 소모한다고 합니다.

 

 

 

Achilles heel in Bentley-Mcllroy implementation (Java system out)

 

 

System sort: Which algorithm to use?

지금까지 배운 것 이외에도 엄청나게 다양한 정렬 알고리즘들이 존재합니다.

이중에서 어떤 것을 사용하는지는 각 상황에 따라 다르다고 볼 수 있습니다.

그럼에도 불구하고 내장 정렬 함수의 성능이 좋은 편인지에 대해 의문을 품는다면 그렇다고 대답할 수 있습니다.

실제로 파이썬을 다룰 때에도 어떤 정렬 함수를 구현하는 것보다 내장 함수를 사용하는 것이 훨씬 효과적일 때가 압도적으로 많습니다.

 

 

Sorting summary

 

 

 

출처: Coursera, Algorithms, Part 1, Princeton University