/* | |
* | |
* compile: gcc quicksort.c | |
* test: ./a.out | |
* | |
*/ | |
#include <stdio.h> | |
enum { SIZE = 9 }; | |
void quicksort(int *target, int left, int right) { | |
if(left >= right) return; | |
int i = left, j = right; | |
int tmp, pivot = target[i]; | |
for(;;) { | |
while(target[i] < pivot) i++; | |
while(pivot < target[j]) j--; | |
if(i >= j) break; | |
tmp = target[i]; target[i] = target[j]; target[j] = tmp; | |
i++; j--; | |
} | |
quicksort(target, left, i-1); | |
quicksort(target, j+1, right); | |
} | |
int main() { | |
int i, array[SIZE] = { 2, 6, 3, 8, 5, 4, 1, 9, 7 }; | |
quicksort(array, 0, SIZE-1); | |
for(i=0; i<SIZE; i++) | |
printf("%d ", array[i]); | |
printf("\n"); | |
} |
% | |
% test: latex quicksrot.tex | |
% | |
\makeatletter | |
% new if and new counts | |
\newif\if@q@loop@ | |
\newcount\q@i | |
\newcount\q@j | |
\newcount\q@pivot | |
% macros for array | |
\def\array#1#2{\csname #1@#2\endcsname} | |
\def\defarray#1#2#3{\expandafter\xdef\csname #1@#2\endcsname{#3}} | |
% quick sort | |
\def\quicksort#1#2#3{% #1: array name, #2: left, #3:right | |
\ifnum#2<#3\relax | |
\bgroup | |
\q@i#2\q@j#3\relax | |
\q@pivot\array{#1}{\the\q@i}% | |
\@q@loop@true | |
\@whilesw\if@q@loop@\fi{% | |
\@whilenum\array{#1}{\the\q@i}<\q@pivot\do{\advance\q@i\@ne}% | |
\@whilenum\q@pivot<\array{#1}{\the\q@j}\do{\advance\q@j\m@ne}% | |
\ifnum\q@i<\q@j | |
\edef\q@tmp{\array{#1}{\the\q@i}}% | |
\defarray{#1}{\the\q@i}{\array{#1}{\the\q@j}}% | |
\defarray{#1}{\the\q@j}{\q@tmp}% | |
\advance\q@i\@ne\advance\q@j\m@ne | |
\else | |
\@q@loop@false | |
\fi}% | |
\advance\q@i\m@ne\advance\q@j\@ne | |
\edef\q@right{\the\q@i}% | |
\quicksort{#1}{#2}{\q@right}% | |
\edef\q@left{\the\q@j}% | |
\quicksort{#1}{\q@left}{#3}% | |
\egroup | |
\fi} | |
% test | |
\def\numlist{2,6,3,8,5,4,1,9,7} | |
\@tempcnta\z@\@tempcntb\z@ | |
\@for\member:=\numlist\do{% | |
\defarray{test}{\the\@tempcnta}{\member}% | |
\advance\@tempcnta\@ne} | |
\quicksort{test}{0}{8} | |
\typeout{Result:} | |
\@whilenum\@tempcnta>\@tempcntb\do{% | |
\message{\array{test}{\the\@tempcntb}}% | |
\advance\@tempcntb\@ne} | |
\@@end |
" | |
" test: vim -S quicksort.vim | |
" | |
" quick sort | |
function! s:quicksort(target, left, right) | |
if a:left >= a:right | return [a:target[a:left]] | endif | |
let i = a:left | let j = a:right | |
let pivot = a:target[i] | |
while 1 | |
while a:target[i] < pivot | let i += 1 | endwhile | |
while pivot < a:target[j] | let j -= 1 | endwhile | |
if i >= j | break | endif | |
let tmp = a:target[i] | let a:target[i] = a:target[j] | let a:target[j] = tmp | |
let i += 1 | let j -= 1 | |
endwhile | |
let l_list = s:quicksort(a:target, a:left, i-1) | |
let r_list = s:quicksort(a:target, j+1, a:right) | |
return l_list + r_list | |
endfunction | |
" test | |
let list = [ 2, 6, 3, 8, 5, 4, 1, 9, 7 ] | |
echo "Result:" | |
echo s:quicksort(list, 0, len(list)-1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
on 100000 value it does not work !!
i have the same problem with my algo