2018년 4월 9일 월요일

[quicksort] 퀵소트 (quicksort with C / Python)

C-language


main.c

#include 
#include 
#include 

#include "selection_sort.h"
#include "quicksort.h"

void printArray(int value[], int count);

int main()
{
    int values[] = { 80, 75, 10, 60, 15, 49, 12, 25 };
    int count = sizeof(values)/sizeof(int);


    printf("quicksort\n");
    // selection_sort(values, count);
    quicksort(values, count);
    printArray(values, count);
    return 0;
}


void printArray(int value[], int count)
{
    int i = 0;
    for(i = 0; i < count; i++) {
        printf("%d ", value[i]);
    }
    printf("\n");
}

quicksort.h

#ifndef QUICKSORT_H_INCLUDED
#define QUICKSORT_H_INCLUDED

void quicksort(int* value, int count);
void _quicksort(int* value, int start, int end);
int quicksort_division(int* value, int left, int right);
void swap(int* left, int* right);
#endif // QUICKSORT_H_INCLUDED

quicksort.c

#include 
#include "quicksort.h"

void quicksort(int* value, int count)
{
    _quicksort(value, 0, count -1);
}

void _quicksort(int* value, int start, int end)
{
    int pivot = 0;

    if (start < end) {
        pivot = quicksort_division(value, start, end);
        _quicksort(value, start, pivot - 1);
        _quicksort(value, pivot+1, end);
    }
}

int quicksort_division(int* value, int left, int right)
{
    int pivot = left;

    while(left = value[pivot]) && (left < right))
            right--;

        if(left < right)
        {
            swap(&value[left], &value[right]);
        }
    }

    swap(&value[pivot], &value[right]);

    return left;
}
void swap(int* left, int* right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

Python

def quicksort(arr):
    _quicksort(arr, 0, len(arr)-1)

def _quicksort(arr, start, end):
    if start < end:
        pivot = _quicksort_division(arr, start, end)
        _quicksort(arr, start, pivot-1)
        _quicksort(arr, pivot+1, end)

def _quicksort_division(arr, left, right):
    pivot = left
    while left < right:
        while arr[left] < arr[pivot] and left < right:
            left += 1
        while arr[right] >= arr[pivot] and left < right:
            right -= 1

        if left < right:
            arr[left], arr[right] = arr[right], arr[left]

    arr[left], arr[pivot] = arr[pivot], arr[left]

    return left

a = [80, 75, 10, 60, 15, 49, 12, 25]

quicksort(a)

댓글 없음 :

댓글 쓰기