비재귀식으로 구현해봤는데 너무 어려웟읍니다..스택 오버플로우가 너무 무서워서 어떻게든 비재귀로 구현해보고 싶었음
재귀식으로 반씩 쪼개가면서 하는 정렬보단 한 두 바퀴 정도는 더 도는 거 같아서 아쉽지만 비재귀로 구현은 성공해서 기분이 좋음.
지금까지 버블, 선택, 삽입, 이진트리, 병합 정렬 이렇게 구현해봤는데 배열 크기가 작을 땐 삽입이 압도적으로 빠르고
배열이 50개 정도만 넘어가도 이진트리랑 병합 정렬이 더 빨라지는 걸 볼 수 있었읍니다..
한 바퀴 돌 때마다 복사용 배열에 또 값들을 복사해서 넣는 게 낭비 같은데 이건 좀 더 고민해봐야 할 문제인 것 같음..
다음 목표는 퀵 정렬이고 그 다음은 한동안 내버려뒀던 RBT 구현할 거예용 오홍홍
그나저나 삼항연산자 처음 써봤는데 너무 좋네요 너무 유용해서 자주 쓰게 될 듯
해당 댓글은 삭제되었습니다.
오잉 그럼 비재귀로 만든 건 뻘짓이었던 건가.. 퀵 정렬도 비재귀로 구현해볼라 합니당
일단 테스트는 좀 돌려봤는데 랜덤 수 5만개까지는 정렬이 되더라고여 그 이상은 랜덤 함수가 스택 오버플로우가 나서... 그 외엔 정렬 잘 되는 거 같아욤 - dc App
해당 댓글은 삭제되었습니다.
임의의 값을 rand()로 넣었는데 5만회 넘기니까 스택 오버플로우가 터지더라고요... - dc App
잉 그냥 크키만 정하고 최대값부터 역순으로 집어넣는 방식으로 시험해봐야겟네여 - dc App
아 그런 설정이 있구나 감사합니당 - dc App
자고 일어나서 알아보니까 정렬 속도 비교용으로 만든 배열들이 많아서 스택으로 다 감당 안된거였어용 일부를 적당히 동적 배열로 옮기니까 더 큰 수도 되네요
fft 재귀를 비재귀로 만들 때 bit reverse 사용했는데 머지소팅도 이거 쓰면 안될까??
생소한 개념이라 알아봐야겟네여 - dc App
퀵 정렬이 빠른 건 맞지만 제가 가장 이상적으로 생각하는 것은 힙 정렬같이 꼼수 안부리는 순수한 알고리즘이 좋아요
힙 정렬은 배열 말고 트리로 만들여보려고 했는데 완전 이진 트리로 만드는 것부터가 골때리더라구용