shell sort, C++ (gcc)

shell sort

//Microsoft (R) C/C++ Optimizing Compiler Version 19.00.23506 for x86

#include <iostream>

int A[] = {12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,2912,2,3,5,7,9,10,43,23,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29,6786,3,3254,789,29,12,2,3,5,7,9,10,43,23,6786,3,3254,789,29};
int N = sizeof(A) / sizeof(A[0]);

void print () 
{
    for (int i=0;i<N;i++)
    {
        std::cout << A[i] << " ";
    }
}

void swap(int &x, int &y) 
{
    int temp = x;
        x = y;
        y = temp;
}

// quick sort
int getIndex (int low, int high) 
{
    int value = A[high];
    int i = low;
    for(int j=low; j<high;j++)
    {
        if(A[j] <= value) 
        {
            swap(A[i], A[j]);
            i++;
        }
    }
    
    swap(A[i], A[high]);
    return (i);
}

void quickSort(int low, int high) 
{
    if(low < high) 
    {
        int index = getIndex(low, high);
        quickSort(low, index - 1);
        quickSort(index + 1, high);
    }
}

// merge sort
void merge (int left, int mid, int right)
{
    int index = left;
    int k = mid - left + 1, m = right - mid, i,j;
    int tempLeft[k];
    int tempRight[m];
    for (i = 0; i < k; i++) 
    {
        tempLeft[i] = A[i + left];
    }
    
    for (j = 0; j < m; j++) 
    {
        tempRight[j] = A[j + mid + 1];
    }
    
    i = 0, j = 0;   
    while (i < k && j < m)
    {
        if(tempLeft[i] < tempRight[j])
        {
            A[index++] = tempLeft[i];
            i++;
        } 
        else
        {
            A[index++] = tempRight[j];
            j++;
        }
    }
    
    while (i < k)
    {
        A[index++] = tempLeft[i];
        i++;
    }
    
    while (j < m)
    {
        A[index++] = tempRight[j];
        j++;
    }
}

void mergeSort (int left, int right)
{
    if(left < right)
    {
        int mid = (right + left) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }
}

// insert sort
void insertSort() 
{
    for(int i = 0; i < N; i++)
    {
        int temp = A[i];
        int j = i;
        while (j > 0 && A[j] < A[j - 1] && j < N)
        {
            A[j] = A[j - 1];
            A[j - 1] = temp;
            j--;
        }
    }
}

// bubble sort
void bubbleSort ()
{
    for(int i = 0; i < N; i++) 
    {
        for (int j = i + 1; j < N; j++)
        {
            if(A[i] > A[j]) {
                swap(A[i], A[j]);
            }
        }
    }
}

// selection sort
void selectionSort ()
{
    for (int i = 0; i < N; i++)
    {
        int MIN = i;
        int j = i + 1;
        while (j < N)
        {
            if(A[j] < A[MIN])
            {
                MIN = j;
            }
            j++;
        }
        if(MIN != i) {
            swap(A[i], A[MIN]);
        }
    }
}

// shell sort
void shellSort () 
{
    
    int interval = N / 2;
    
    while (interval > 0)
    {
        for (int innerIndex = interval; innerIndex < N; innerIndex++) 
        {
            int valueInsert = A[innerIndex];
            int j = innerIndex;
            if (A[j] < A[j - interval]) 
            {
                A[j] = A[j - interval];
                A[j - interval] = valueInsert;
            }
        }
        
        interval--;
    }
    
    
    /*
    int i, j, k, temp;
	// Gap 'i' between index of the element to be compared, initially n/2.
	for(i = N/2; i > 0; i = i/2)
	{
		for(j = i; j < N; j++)
		{
			for(k = j-i; k >= 0; k = k-i)
			{
				// If value at higher index is greater, then break the loop.
				if(A[k+i] >= A[k])
				break;
				// Switch the values otherwise.
				else
				{
					temp = A[k];
					A[k] = A[k+i];
					A[k+i] = temp;
				}
			}
		}
	}
    */
}

void menu ()
{
    std::cout << "Enter choice: \n";
    std::cout << "1. Quick sort \n";
    std::cout << "2. Merge sort \n";
    std::cout << "3. Insert sort \n";
    std::cout << "4. Bubble sort \n";
    std::cout << "5. Selection sort \n";
    std::cout << "6. Shell sort \n";
    std::cout << "0. Exit \n";
    int choice;
    std::cin >> choice;
    switch (choice)
        {
            case 1:
                std::cout << "Quick sort\n";
                quickSort(0, N-1);
                break;
            case 2:
                std::cout << "Merge sort\n";
                mergeSort(0, N-1);
                break;
            case 3:
                std::cout << "Insert sort\n";
                insertSort();
                break;
            case 4:
                std::cout << "Bubble sort\n";
                bubbleSort();
                break;
            case 5:
                std::cout << "Selection sort\n";
                selectionSort();
                break;
            case 6:
                std::cout << "Shell sort\n";
                shellSort();
                break;
            case 0:
                std::cout << "Exit";
                exit(0);
                break;
            default:
                std::cout << "Please input again...";
                break;
        }
    print();
}

int main()
{
    menu();
    return 0;
}


run \| edit \| history \| help	0