Skip to content

Instantly share code, notes, and snippets.

@wtsnjp
Last active July 13, 2020 05:59
Show Gist options
  • Save wtsnjp/53222131fd86824858fc0b37cd9db98a to your computer and use it in GitHub Desktop.
Save wtsnjp/53222131fd86824858fc0b37cd9db98a to your computer and use it in GitHub Desktop.
/*
*
* 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)
@zakigatez
Copy link

on 100000 value it does not work !!
i have the same problem with my algo

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment