https://www.udemy.com/course/best-javascript-data-structures/
테스트 값
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
public class SortEx01 {
public static void main(String[] args) {
ThreadLocalRandom current = ThreadLocalRandom.current();
Integer[] array = current.ints(0,300).distinct().limit(10).boxed().toArray(Integer[]::new);
System.out.println(array.getClass().getSimpleName()+" "+ Arrays.toString(array));
//정렬들 저장용
List<SortStategy<Integer>> list = new ArrayList<>();
for(SortStategy<Integer> sort : list)
System.out.printf("%-20s %s%n",sort.getClass().getSimpleName(),
Arrays.toString(sort.sort(array)));
}
static interface SortStategy<T>{
T[] sort(T[] arr);
//자리 바꿈 메서드
default void swap(Integer[] clone, int i, int j) {
Integer tmp = clone[i];
clone[i] = clone[j];
clone[j] = tmp;
}
}
}버블 정렬
큰 값을 뒤로 보내며, 최대반복 수를 점점 줄여간다.
static class BubbleSort implements SortStategy<Integer>{
static int cnt = 0;
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
for(int i=0;i<clone.length-1;i++) {// n -1 번 수행
for(int j=1;j<clone.length-i;j++) {
cnt++;
if(clone[j]<clone[j-1]) {
swap(clone, j-1, j);
}
}
System.out.println(Arrays.toString(clone));
}
System.out.print("버블소트 cnt("+cnt+")");
return clone;
}
}Integer[] [113, 247, 171, 173, 243, 35, 66, 223, 85, 83]
[113, 171, 173, 243, 35, 66, 223, 85, 83, 247]
[113, 171, 173, 35, 66, 223, 85, 83, 243, 247]
[113, 171, 35, 66, 173, 85, 83, 223, 243, 247]
[113, 35, 66, 171, 85, 83, 173, 223, 243, 247]
[35, 66, 113, 85, 83, 171, 173, 223, 243, 247]
[35, 66, 85, 83, 113, 171, 173, 223, 243, 247]
[35, 66, 83, 85, 113, 171, 173, 223, 243, 247]
[35, 66, 83, 85, 113, 171, 173, 223, 243, 247]
[35, 66, 83, 85, 113, 171, 173, 223, 243, 247]
버블소트 cnt(45)BubbleSort [35, 66, 83, 85, 113, 171, 173, 223, 243, 247]최대 값이 제일 뒤로 가니, 그에 따라 최대 반복 수를 줄여 정렬한다.
버블 정렬 최적화
static class BubbleSortOp implements SortStategy<Integer>{
Boolean noSwap = false;
static int cnt = 0;
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
for(int i=0;i<clone.length-1;i++) {// n -1 번 수행용 반복문
noSwap = true;
for(int j=1;j<clone.length-i;j++) {//자리바꿈 루프
cnt++;
if(clone[j]<clone[j-1]) {
noSwap = false; // 자리바꿈이 한 번이라도 수행됐다.
swap(clone, j-1, j);
}
}
if(noSwap) break; //자리 바꿈이 수행된적이 없으면 수행용 반복은 의미없음
}
System.out.print("버블소트 최적화 cnt("+cnt+")");
return clone;
}
}더 이상 교환된 값이 없으면, 더 이상 정렬한 값이 없는 것으로 반복문을 빠져나온다.
Integer[] [286, 172, 22, 197, 169, 62, 236, 99, 141, 156]
버블소트 cnt(45)BubbleSort [22, 62, 99, 141, 156, 169, 172, 197, 236, 286]
버블소트 최적화 cnt(39)BubbleSortOp [22, 62, 99, 141, 156, 169, 172, 197, 236, 286]선택 정렬
지정된 위치에 최적에 값을 넣는다.
가장 안 좋은 정렬이다. 어떠한 경우에도 n^2 시간 복잡도를 보인다.
//버블 정렬보다 나은 점은 스왑수 최소화, i루프 마다 단 한번의 스왑만 발생
static class SelectionSort implements SortStategy<Integer>{
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
for(int i=0;i<clone.length-1;i++) {
for(int j=i+1;j<clone.length;j++) {
if(Integer.compare(clone[i], clone[j])>0) {
swap(clone, i, j);
}
}
}
return clone;
}
}삽입 정렬
논리적으로 배열안에 서브 배열을 만들어 점차 정렬해가는 정렬
배열의 요소가 1개면, 자연스럽게 정렬된 상태다. 즉, 배열의 요소가 2개부터 정렬이 가능한 상태로 시작 인덱스는 1로 준다.
배열의 요소가 거의 정렬된 상태일 때 매우 빠른 속도를 보인다.
static class InsertSort implements SortStategy<Integer>{
//논리적으로 순회 마다 작은 서브배열을 만든다고 가정한다.
//1부터 시작
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
//배열이 단 한개는 이미 정렬된 것이다. (논리적 배열)
for(int i = 1;i<clone.length;i++) {
//배열 shift 하는 동안 값 손실 때문이 임시 저장
Integer newMember = clone[i];
Integer j = i-1;
//새로운 멤버 clone[i]
for(;j>=0 && newMember < clone[j];j--) {
clone[j+1] = clone[j];
}
//들어갈 자리 j-- 보정 값 +1
clone[j+1] = newMember;
}
return clone;
}
}전체 코드
package udemyjavascript;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
public class SortEx01 {
public static void main(String[] args) {
ThreadLocalRandom current = ThreadLocalRandom.current();
Integer[] array = current.ints(0,300).distinct().limit(10).boxed().toArray(Integer[]::new);
System.out.println(array.getClass().getSimpleName()+" "+ Arrays.toString(array));
//정렬들 저장용
List<SortStategy<Integer>> list = new ArrayList<>();
list.add(new BubbleSort());
list.add(new BubbleSortOp());
list.add(new SelectionSort());
// list.add(new InsertSort());
for(SortStategy<Integer> sort : list)
System.out.printf("%-20s %s%n",sort.getClass().getSimpleName(),
Arrays.toString(sort.sort(array)));
}
static interface SortStategy<T>{
T[] sort(T[] arr);
//자리 바꿈 메서드
default void swap(Integer[] clone, int i, int j) {
Integer tmp = clone[i];
clone[i] = clone[j];
clone[j] = tmp;
}
}
static class BubbleSort implements SortStategy<Integer>{
static int cnt = 0;
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
for(int i=0;i<clone.length-1;i++) {// n -1 번 수행
for(int j=1;j<clone.length-i;j++) {
cnt++;
if(clone[j]<clone[j-1]) {
swap(clone, j-1, j);
}
}
}
System.out.print("버블소트 cnt("+cnt+")");
return clone;
}
}
static class BubbleSortOp implements SortStategy<Integer>{
Boolean noSwap = false;
static int cnt = 0;
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
for(int i=0;i<clone.length-1;i++) {// n -1 번 수행용 반복문
noSwap = true;
for(int j=1;j<clone.length-i;j++) {//자리바꿈 루프
cnt++;
if(clone[j]<clone[j-1]) {
noSwap = false; // 자리바꿈이 한 번이라도 수행됐다.
swap(clone, j-1, j);
}
}
if(noSwap) break; //자리 바꿈이 수행된적이 없으면 수행용 반복은 의미없음
}
System.out.print("버블소트 최적화 cnt("+cnt+")");
return clone;
}
}
//버블 정렬보다 나은 점은 스왑수 최소화, i루프 마다 단 한번의 스왑만 발생
static class SelectionSort implements SortStategy<Integer>{
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
for(int i=0;i<clone.length-1;i++) {
for(int j=i+1;j<clone.length;j++) {
if(Integer.compare(clone[i], clone[j])>0) {
swap(clone, i, j);
}
}
}
return clone;
}
}
static class InsertSort implements SortStategy<Integer>{
//논리적으로 순회 마다 작은 서브배열을 만든다고 가정한다.
//1부터 시작
public Integer[] sort(Integer[] arr) {
Integer[] clone = arr.clone();
//배열이 단 한개는 이미 정렬된 것이다. (논리적 배열)
for(int i = 1;i<clone.length;i++) {
//배열 shift 하는 동안 값 손실 때문이 임시 저장
Integer newMember = clone[i];
Integer j = i-1;
//새로운 멤버 clone[i]
for(;j>=0 && newMember < clone[j];j--) {
clone[j+1] = clone[j];
}
//들어갈 자리 j-- 보정 값 +1
clone[j+1] = newMember;
}
return clone;
}
}
}Integer[] [297, 76, 286, 161, 206, 20, 61, 160, 3, 9]
버블소트 cnt(45)BubbleSort [3, 9, 20, 61, 76, 160, 161, 206, 286, 297]
버블소트 최적화 cnt(45)BubbleSortOp [3, 9, 20, 61, 76, 160, 161, 206, 286, 297]
SelectionSort [3, 9, 20, 61, 76, 160, 161, 206, 286, 297]
정렬 속도 비교
https://www.toptal.com/developers/sorting-algorithms
Sorting Algorithms Animations
Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions.
www.toptal.com