 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
sorting procedures        Author Message
zylum  Posted: Wed Mar 10, 2004 9:14 pm   Post subject: sorting procedures

here's a small list i have compiled of simple sorting algorithms...

 code: %swap and shift procedures procedure swap (var list : array 1 .. * of int, i, j : int)     const temp := list (i)     list (i) := list (j)     list (j) := temp end swap procedure shift (var list : array 1 .. * of int, i, j : int)     const temp := list (j)     for decreasing k : j .. i + 1         list (k) := list (k - 1)     end for     list (i) := temp end shift %insertion sort procedure insertionSort (var list : array 1 .. * of int)     for j : 2 .. upper(list)         var i := 1         loop             exit when i = j or list (i) >= list (j)             i += 1         end loop         shift (list, i, j)     end for end insertionSort %selection sort procedure selectionSort (var list : array 1 .. * of int)     for i : 1 .. upper(list) - 1         var locationOfSmallest := i         for j : i + 1 .. upper(list)             if list (j) <= list (locationOfSmallest) then                 locationOfSmallest := j             end if         end for         swap (list, i, locationOfSmallest)     end for end selectionSort %bubble sort procedure bubbleSort (var list : array 1 .. * of int)     for j : 1 .. upper(list) - 1         const last := upper(list) - j + 1         for k : 1 .. last - 1             if list (k) > list (k + 1) then                 swap (list, k, k + 1)             end if         end for     end for end bubbleSort %merge sort procedure merge (var list : array 1 .. * of int, first, middle, last : int)     var temp : array 1 .. last of int     var point1 := first     var point2 := middle + 1     var point3 := first     loop         exit when point3 > last         if point1 < middle + 1 and (point2 > last or list (point1) < list (point2)) then             temp (point3) := list (point1)             point1 := point1 + 1         else             temp (point3) := list (point2)             point2 := point2 + 1         end if         point3 += 1     end loop     for i : first .. last         list (i) := temp (i)     end for end merge procedure mergeSort (var list : array 1 .. * of int, first, last : int)     if last > first then         const middle := (first + last) div 2         mergeSort (list, first, middle)         mergeSort (list, middle + 1, last)         merge (list, first, middle, last)     end if end mergeSort %quick sort procedure quickSort (var list : array 1 .. * of int, left, right : int)     var pivotPlace : int     swap (list, left, (left + right) div 2)     var lastSmall := left     for i : left + 1 .. right         if list (i) <= list (left) then             lastSmall += 1             swap (list, lastSmall, i)         end if     end for     swap (list, left, lastSmall)     pivotPlace := lastSmall     if left < pivotPlace - 1 then         quickSort (list, left, pivotPlace - 1)     end if     if pivotPlace + 1 < right then         quickSort (list, pivotPlace + 1, right)     end if end quickSort %main proggy %create random data var numbers : array 1 .. 10 of int put "unsorted:" : 10 .. for i : 1 .. 10     numbers (i) := Rand.Int (1, 1000)     put numbers (i) : 5 .. end for %insertionSort (numbers, 10) %selectionSort (numbers, 10) %bubbleSort (numbers, 10) %mergeSort (numbers, 1, 10) quickSort (numbers, 1, 10) put "\n\nsorted:" : 12 .. for i : 1 .. 10     put numbers (i) : 5 .. end for

-zylum    Catalyst  Posted: Wed Mar 10, 2004 9:26 pm   Post subject: (No subject)

heres a qSort that retains an associated index array (proves to be useful)
 code: procedure qSort (var a : array 1 .. * of real, var b : array 1 .. * of int, l, h : int)     if l < h then         var aH : real         var bH : int         var i : int := l;         var j : int := h         var mid : real := a (l)         loop             loop                 exit when a (i) >= mid                 i += 1             end loop             loop                 exit when a (j) <= mid                 j -= 1             end loop             if i <= j then                 aH := a (i)                 a (i) := a (j)                 a (j) := aH                 bH := b (i)                 b (i) := b (j)                 b (j) := bH                 i += 1                 j -= 1             end if             exit when i > j         end loop         qSort (a, b, l, j)         qSort (a, b, i, h)     end if end qSort

and heres a shell sort

 code: proc Shell (var numbers : array 0 .. * of real, arraysize : int)         var j, increment : int         var temp, temp2 : real         increment := 3         loop             locate (1, 1)             put increment             if increment > 0 then                 for i : 0 .. arraysize                     j := i                     temp := numbers (i)                     loop                         if (j >= increment) and (numbers (j - increment) > temp) then                             numbers (j) := numbers (j - increment);                             j := j - increment;                         else                             exit                         end if                     end loop                     numbers (j) := temp                 end for                 if (increment / 2 not= 0) then                     increment := increment div 2;                 elsif (increment = 1) then                     increment := 0                 else                     increment := 1                 end if             else                 exit             end if         end loop     end Shell Delos  Posted: Fri Mar 12, 2004 12:57 pm   Post subject: (No subject)

Ah, sorting...how we love thee.

Number sorts are good...how about word sorts? Hehehe...have fun with those... Tony  Posted: Fri Mar 12, 2004 3:54 pm   Post subject: (No subject) sorting words is the same as numbers cuz you can compare them alphabetically... or to be more accurate, ASCII values of characters
 code: if "tony" > "dan" then put "score" else put "boo" end if Tony's programming blog. DWITE - a programming contest. zylum  Posted: Fri Mar 12, 2004 6:04 pm   Post subject: (No subject)

yeah so for the sorts listed above, turn all variable types form int to string. well almost all...

-zylum the_short1  Posted: Sun Mar 14, 2004 6:45 pm   Post subject: (No subject)

yea sorting programsd are fun... ive had to make a couple in my day.... and to convert from oen to another is ez...

if word > bigword then
bigword = word

so realy u can convert all the strings to int to make it work for umbers.... i did that... saved me a lot of type for assignments.. one week in our questions we had to make a word sort.. enxt week one of our questions was to make a number sort... as soon as the teacher said that... i said... what do i do now.. im done..        whiole the clas was toiling away SuperGenius Posted: Mon Mar 15, 2004 3:06 pm   Post subject: (No subject)

so if I wanted to sort an array of string I could just use a bubble sort? zylum  Posted: Mon Mar 15, 2004 3:10 pm   Post subject: (No subject)

yup, but in the procedure the arguments need to be string not int...

-zylum    SuperGenius Posted: Mon Mar 15, 2004 8:42 pm   Post subject: (No subject)

cool.... I was going to add a high score list to my connect 4 game which rules by the way, but then I didnt becuase I didnt know how, so mabye I will now. GlobeTrotter Posted: Sat Mar 12, 2005 10:28 pm   Post subject: (No subject)

Here's a program that compares the sorting times of those originally posted.

 code: %swap and shift procedures procedure swap (var list : array 1 .. * of int, i, j : int)     const temp := list (i)     list (i) := list (j)     list (j) := temp end swap procedure shift (var list : array 1 .. * of int, i, j : int)     const temp := list (j)     for decreasing k : j .. i + 1         list (k) := list (k - 1)     end for     list (i) := temp end shift %insertion sort procedure insertionSort (var list : array 1 .. * of int)     for j : 2 .. upper (list)         var i := 1         loop             exit when i = j or list (i) >= list (j)             i += 1         end loop         shift (list, i, j)     end for end insertionSort %selection sort procedure selectionSort (var list : array 1 .. * of int)     for i : 1 .. upper (list) - 1         var locationOfSmallest := i         for j : i + 1 .. upper (list)             if list (j) <= list (locationOfSmallest) then                 locationOfSmallest := j             end if         end for         swap (list, i, locationOfSmallest)     end for end selectionSort %bubble sort procedure bubbleSort (var list : array 1 .. * of int)     for j : 1 .. upper (list) - 1         const last := upper (list) - j + 1         for k : 1 .. last - 1             if list (k) > list (k + 1) then                 swap (list, k, k + 1)             end if         end for     end for end bubbleSort %merge sort procedure merge (var list : array 1 .. * of int, first, middle, last : int)     var temp : array 1 .. last of int     var point1 := first     var point2 := middle + 1     var point3 := first     loop         exit when point3 > last         if point1 < middle + 1 and (point2 > last or list (point1) < list (point2)) then             temp (point3) := list (point1)             point1 := point1 + 1         else             temp (point3) := list (point2)             point2 := point2 + 1         end if         point3 += 1     end loop     for i : first .. last         list (i) := temp (i)     end for end merge procedure mergeSort (var list : array 1 .. * of int, first, last : int)     if last > first then         const middle := (first + last) div 2         mergeSort (list, first, middle)         mergeSort (list, middle + 1, last)         merge (list, first, middle, last)     end if end mergeSort %quick sort procedure quickSort (var list : array 1 .. * of int, left, right : int)     var pivotPlace : int     swap (list, left, (left + right) div 2)     var lastSmall := left     for i : left + 1 .. right         if list (i) <= list (left) then             lastSmall += 1             swap (list, lastSmall, i)         end if     end for     swap (list, left, lastSmall)     pivotPlace := lastSmall     if left < pivotPlace - 1 then         quickSort (list, left, pivotPlace - 1)     end if     if pivotPlace + 1 < right then         quickSort (list, pivotPlace + 1, right)     end if end quickSort %main proggy %create random data var numbers : array 1 .. 500 of int var timeUsed : array 0 .. 5 of int var speed : array 1 .. 5 of int sysclock (timeUsed (0)) for i : 1 .. upper (numbers)     numbers (i) := Rand.Int (1, 1000) end for insertionSort (numbers) sysclock (timeUsed (1)) for i : 1 .. upper (numbers)     numbers (i) := Rand.Int (1, 1000) end for selectionSort (numbers) sysclock (timeUsed (2)) for i : 1 .. upper (numbers)     numbers (i) := Rand.Int (1, 1000) end for bubbleSort (numbers) sysclock (timeUsed (3)) for i : 1 .. upper (numbers)     numbers (i) := Rand.Int (1, 1000) end for mergeSort (numbers, lower (numbers), upper (numbers)) sysclock (timeUsed (4)) for i : 1 .. upper (numbers)     numbers (i) := Rand.Int (1, 1000) end for quickSort (numbers, lower (numbers), upper (numbers)) sysclock (timeUsed (5)) for i : 1 .. 5     speed (i) := timeUsed (i) - timeUsed (i - 1) end for put "Insertion Sort: ", speed(1) put "Selection Sort: ", speed(2) put "Bubble Sort: ", speed(3) put "Merge Sort: ", speed(4) put "Quick Sort: ", speed(5) Mr. T  Posted: Mon Mar 28, 2005 12:47 am   Post subject: (No subject)

can u gimme examples of progs that u would need to use sorting (aside from high score lists) Weelkid_29 Posted: Mon Jan 23, 2006 8:05 pm   Post subject: (No subject)

i need help sorting strings alphabetically blaster009 Posted: Mon Jan 23, 2006 8:33 pm   Post subject: (No subject)

It's really not difficult...Turing handles String comparisons just like it does integer comparisons. Just change the data types to strings.

Here's my sorting algorithms:

 code: % Swap Procedure proc swap (var swapArray : array 0 .. * of int, swapNumOne : int, swapNumTwo : int)     var tempNum : int     tempNum := swapArray (swapNumOne)     swapArray (swapNumOne) := swapArray (swapNumTwo)     swapArray (swapNumTwo) := tempNum end swap % Bubble Sort - Only NINE lines! proc bubbleSort (var sortArray : array 0 .. * of int)     for i : lower (sortArray) .. upper (sortArray)         for j : lower (sortArray) + 1 .. upper (sortArray)             if sortArray (j) <= sortArray (j - 1) then                 swap (sortArray, j, j - 1)             end if         end for     end for end bubbleSort % Selection Sort - Only ELEVEN lines! proc selectSort (var sortArray : array 0 .. * of int)     var sortNum : int := lower (sortArray)     for i : lower (sortArray) .. upper (sortArray)         for j : lower (sortArray) .. upper (sortArray) - i             if sortArray (j) >= sortArray (sortNum) or j = lower (sortArray) then                 sortNum := j             end if         end for         swap (sortArray, sortNum, upper (sortArray) - i)     end for end selectSort

I'm quite proud of my Bubble Sort  person Posted: Tue Jan 24, 2006 8:06 pm   Post subject: (No subject)

no offense, but bubble and selection sort kinda sux Clayton  Posted: Wed Jan 25, 2006 8:17 am   Post subject: (No subject)

Pwned wrote:
can u gimme examples of progs that u would need to use sorting (aside from high score lists)

mostly databases, records, ect. they can be used quite a bit, especially for a teacher b/c they have to go through hundreds of marks (too bad for them   ) Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Page 1 of 2  [ 27 Posts ]
Goto page 1, 2  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: