🎯시작 전 목표

1. 정렬 알고리즘 공부

💻Today I learned

✔ 여러가지 종류의 정렬과 시간복잡도

모든 정렬은 오름차순 기준으로 한다.

• # O(n²) 인 정렬들

• 선택 정렬
  굳이 코드가 아니더라도 인간이 무언가를 정렬할 때 본능적으로 사용하게 되는 정렬방식중 하나로, 정렬의 무작위성과 상관없이 일관적으로 같은 시간이 걸린다는 특징이 있다.

    public int[] Selection(int[] arr)
    {
    		for(int i=0; i<arr.length-1; i++)
   		{
  			for(int j=i; j<arr.length; j++)
    			{
    				if(arr[i]>arr[j])
    				{
                      int temp=a;
                      a=b;
                      b=temp;  				
  				}
    			}
    		}
    }
  

• 삽입 정렬
  선택 정렬과 함께 인간이 무언가를 정렬할 때 무의식적으로 사용하게 되는 대표적인 알고리즘이다. 배열의 크기가 작을 때의 효율이 뛰어나고, 이미 정렬되어 있는 배열에 삽입 혹은 제거할 때 용이한 정렬방식이다. 덤으로 구현이 매우 쉽다는 장점이 있다.

  public void Inversion(int[] arr)
  {
  		int temp;
  		for(int i=1;i<arr.length;i++)
        {
            temp=arr[i]
        	for(int j=i-1; j>=0 && arr[j]>temp ;j--)
  			{ 
  				arr[j+1]=temp;
  			}
  		}             
  }
  

• 버블 정렬

  최악의 성능을 지닌 정렬로 어떠한 상황이 주어져도 대부분 극악의 효율을 자랑한다. 장점으로는 이해하기 매우 쉽다는 점이 있고, 단점은 이해하는 순간 쓸 일이 없어진다는 점이다.

    public void Bubble(int[] arr)
    {
    		for(int i=0;i<arr.length-1;++i)
  		{
          	for(int j=0;j<arr.length-i-1;++j)
    			{
    				if(arr[j]>arr[j+1])
    				{
                  	temp =arr[j];
                      arr[j]=arr[j+1];
                      arr[j+1]=temp;
  				}
    			}
  		}
    }

• # O(n log n) 인 정렬들(추가 예정)

• 퀵 정렬
  특정 상황을 제외하면 다른 알고리즘에 비해 매우 빠른 속도를 자랑한다.
  추가적인 메모리를 필요로 하지 않으며, 재귀호출의 스택프레임에 의한 공간복잡도는 log n으로 메모리를 적게 소비한다. 단, 특정 조건에서 성능이 버블정렬급으로 급격하게 떨어지며, 재귀를 사용하기 때문에 사용하지 못하는 환경에서의 구현이 매우 복잡해진다는 단점이 있다.

      public void Quick(int[] arr)
      {
          Sort(arr, 0, arr.length-1);
      }
  
      public void Sort(int[] arr, int low, int high)
      {
          if(low>=high) return;
          int pivot =Partition(arr, low, high);
          Sort(arr, low, pivot-1);
          Sort(arr, pivot+1, high);
      }
  
      public int Partition(int[] arr, int left, int right)
      {
          int low= left;
          int high= right;
          int pivot= arr[left];
  
          while(low<high)
          {
              while(arr[high]>pivot && low<high){high--; }
              while(arr[low]<=pivot && low<high){low++; }
              Swap(arr, low, high);
          }
          Swap(arr, left, low);
          return low;
      }
  
      public void Swap(int[] arr, int a, int b)
      {
          int temp=arr[a];
          arr[a]=arr[b];
          arr[b]=temp;
      }