본문 바로가기

Programing(프로그래밍)

C# 퀵 소트

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;


namespace quicksort

{

    class Program

    {

        static void swap(int[] numbers, int a, int b)

        {

            int temp = numbers[a];

            numbers[a] = numbers[b];

            numbers[b] = temp;

        }


        static void sort(int[] numbers, int left, int right)

        {

            if(right <= left)       //exit condition

            {

                return;

            }

            

            int pivot = right;      //rightest bececome a new pivot


            int i = left;

            int j = right-1;


            while(i<j)              //compare with i and j (left and right)

            {

                if(numbers[i]<=numbers[pivot])

                {

                    i++;

                }

                else if(numbers[j] >= numbers[pivot])

                {

                    j--;

                }

                else

                {

                    swap(numbers, i, j);

                    i++;

                }

            }

            int newpivot = j;       //j become a new pivot

            swap(numbers, pivot, newpivot);     //switch a old pivot value and a new pivot



            /////////////////// recursive function

            sort(numbers, newpivot + 1, right);

            sort(numbers, left, newpivot - 1);

            //////////////////

            

        }


        static void Main(string[] args)

        {

            int[] numberArray = { 1, 6, 352, 56, 3, 43, 57, 47, 5, 2, 63, 0, 96 };      //random input

            int length = numberArray.Length;

            sort(numberArray, 0, length - 1);



            ////////////////////print

            Console.WriteLine("Sort result::");

            for(int i = 0; i < length; i++)

            {

                Console.Write("{0} ", numberArray[i]);

            }

            ////////////////////

        }

    }

}





-----------------------------------------
완성하는데 한달 가까이 걸림....
한번 다 완성하고, 집에와서 첨부터 다시 짜보니 30분도 안걸림.....헉

구글에 퀵소트 검색해서 나온 위키페이지만 믿고(예제가 잘못되어 있다...틀린건 아닌데ㅜ)고생하다가
결국은 거의 도움으로 짠듯 ㅠㅠ

여기서 배운건
1. 나는 내가 하고 있는 일을 설명할 줄 모른다(논리력이 부조카다) *중요
2. 퀵소트는 재귀함수다. 재귀함수로만 할 수 있는 일도 있다.
3. 재귀함수를 나가는 조건은(exit condition) 함수의 제일 처음에 있는게 (무조건)좋다.
4. 두 위치을 비교하면서 진행할땐, 한번에 한쪽 위치만 바꿔주는게 좋다. 안그러면 두 위치가 뒤집힐 수 있다.
5. 조금이라도 고쳤으면 디버깅을 하자.
6. 버그가 10개건 100개건 일단 당장 고치려고 하는 버그 하나에만 집중하자. 안그러면 절대 못고친다.
7. 심플하게 만들 수 있는걸 굳이 복잡하게 만들지 말자. 함수 하나만 거치면 될껄 두개 세개를 거치게 하면 더 복잡해진다.
8. 함수를 만들었으면 그 함수를 믿어라. 내가 만든 함수는 내가 넣은 값을 받아서 결과값을 도출해준다. 
일단 만들어진거라면 내부에서 어떻게 값을 도출해 내는지는 중요하지 않다.
9. sort 함수는 "숫자가 들어있는 행렬과 (왼쪽 오른쪽)위치값을 받아서 그 위치사이의 행렬이 가진 값을 정렬"해준다.