정렬알고리즘 - 정렬문제란, 안정정렬, in-place정렬

#정렬알고리즘 #정렬문제 #안정정렬 #inplace정렬

​

AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다.

정렬문제란?

정렬이란 사용자의 의도에 맞게 특정한 순서로 데이터를 정리하는 것을 말합니다. 흔히 사용되는 정수의 오름차순, 내림차순이나 알파벳의 순서(a -> b -> c ...)등과 같은 것들입니다.

​

정렬문제란 정렬 알고리즘을 사용하는 문제를 말하는데, 문제를 정확히 풀어내기 위해선 각 언어에서 구현된 정렬 함수가 어떤 알고리즘을 사용중인지 이해하는 것이 중요합니다.

정렬 알고리즘은 CS면접에서 자주 질문하는 문제중 하나입니다. 어떤 정렬 알고리즘이 있는지, 각 알고리즘의 특징이 무엇인지, 차이는 무엇인지를 중점적으로 공부하는 것이 중요합니다.

​

안정 정렬과 제자리 정렬

본격적으로 정렬 알고리즘에 대해 이해하기전에 안정(stable)정렬과 제자리(in-place)정렬 개념을 이해할 필요가 있습니다.

​

이는 중요하지 않아 보여도 상당히 중요한 개념이니 꼭 익혀 두시는 것을 추천합니다!

안정(stable)정렬

안정(stable)정렬이란?

안정(stable)정렬은 정렬전의 데이터 원소 순서가 정렬 후에도 유지되는 정렬입니다. 그림을 보시면 쉽게 이해하실 수 있습니다.

​

안정정렬은 중복된 값에 대한 상대적인 순서를 유지할 수 있으며, 중간 정렬결과를 사용하여 훨씬 더 복잡한 알고리즘을 만들 수도 있습니다. '

제자리(in-place)정렬

제자리(in-place)정렬이란?

제자리(in-place)정렬은 주어진 정렬안에서 정렬을 수행하는 방법을 말합니다. 따로 배열을 만들지 않아도 되기때문에 공강복잡도에서 이점을 볼 수 있습니다.

​

​