1. bogo sort
직역하면 멍청이 정렬 정도로 번역할 수 있는데,
정렬된 상태가 될 때까지 무작위로 섞는 행동을 반복한다.
n개의 데이터에 대해 기대 시행횟수는 n*n!
2. bogo bogo sort.
bogo sort에 bogo가 하나 더 붙었다.
이 정렬은 bogo sort를 하기 위해 bogo sort를 재귀한다.
조금 더 쉽게 말하면 처음 n-1개의 원소에 대해 bogo bogo sort를 진행하고, 마지막 원소를 포함한 배열이 정렬된 상태인지 확인한다.
만약 정렬된 상태가 아니라면 다시 섞고 반복한다.
더 간단하게 말하면 아무거나 하나 뽑아서 그게 최대 원소이면 n-1개에 대해서 뽑아서 최대인지 확인하고 ... 를 반복하는데
최대인지 확인하기 위해서 나머지를 bogo bogo sort로 정렬해 놓고 검사를 시작한다는 뜻
n개의 데이터에 대해 기대 시행횟수는 약 n!^n!
3. 기수 정렬
말 그대로 기수법을 이용하는 정렬이다.
예를 들어 2진법을 이용하면,
1의 자리가 0인것끼리, 1인것끼리 모은다. 이때 들어온 순서대로 배열한다.
다음으로 2의 자리가 0인것끼리, 1인것 끼리 모은다. 이때도 들어온 순서대로 배열하는데, 1의 자리가 0인 배열에서 먼저 가져온다.
다음으로 4의 자리에 대해서, 8의 자리에 대해서 들어온 순서대로 배열하는 식으로 최대값보다 큰 범위까지 정렬한다.
n개의 k자리수에 대해 시행 횟수는 kn.
