##vbScript - Sorting With and Without Code Please see my post [vbScript - The Basics](https://www.daniweb.com/programming/threads/516400/vbscript-the-basics) for more details on vbScript. Sorting is something that must be done from time to time. I'm going to examine three ways. The first is the well known (at least by name) QuickSort method. Rather than repeating existing explanations of the actual algorithm I'll just refer you to the [Wikipedia QuickSort article](https://en.wikipedia.org/wiki/Quicksort) and present the code with comments below. The second method uses a binary tree. The concept is simple even if the implementation is a little difficult to grasp initially. We start with the …

Member Avatar
+1 forum 0

Over the years I've seen a lot of discussion (and several implementations) of the Quicksort algorithm. Most of what I have seen, unfortunately, lacks sufficient commenting as well as meaningful variable names. Hopefully the following vbScript code will more clearly show how Quicksort actually works. A couple of incidental notes: 1. I use PrimalScript for editing and I have comments set to display with a silver-grey background and black text. This makes comments very distinct from code (and is also why I have a closing single quote at the end of lines). 1. The test code section at the end …

Member Avatar
Member Avatar
+1 forum 6

Hello everyone,i think i know quick sort algorithm.But i need help in figuring out its worst case. Lets look at the below quicksort code----> void quicksort(int arr[],int low,int high) //low and high are pased from main() { int m; if(low<high) { m=partition(arr,low,high); quicksort(arr,low,m-1); quicksort(arr,m+1,high); } } int partition(int arr[],int low,int high) { int pivot=arr[low],i=low,j=high; while(i<j) { while((arr[i]<=pivot)&&(i<=high)) i++; while(arr[j]>pivot) j--; if(i<j) swap(arr,i,j); //swaps arr[i]and arr[j] } swap(arr,low,j); //swaps arr[low] and arr[j] return j; } I am not writing the definition of swap function here as it is self explanatory. Now lets trace the above code for arr 1 2 3 …

Member Avatar
+0 forum 0

I am trying to write several different sorting algorithms in order to time the differences between them when reading a file of a half million integers. For testing purposes, I am only using a few hundred integers, but I am getting a stack overflow error. Also, for testing reasons, I have an output file being created during this run so that I can see if the code is working correctly. Originally, I had 3 nested for loops that I believed were causing the errors (and horrible effeciencey), but I cleaned those up and I am still having the error. Can …

Member Avatar
Member Avatar
+0 forum 4

Hello, What is the best way to count the number of swaps required to sort an array that is sorted using the Quicksort algorithm? I put a counter in what I believe is in the correct position and the tests that I have run seem to be correct however Quicksort is so complex I do not trust my data. Thanks, /** The IntQuickSorter class provides a public static method for performing a QuickSort on an int array. */ public class IntQuickSorter2 { private static int track = 0; /** The quickSort method calls the doQuickSort method to sort an int …

Member Avatar
Member Avatar
+0 forum 5

Hi everyone. I've been struggling with a quicksort implementation here. I think - scratch that - I know i'm overrunning an array (erm, vector) based on how it explodes, but I honestly can't see it and I have no debugger. I slept on it but fresh eyes didn't get me anywhere. I've been digging around online for a while but there are a thousand different ways to do quicksort and it just ends up being confusing to keep it all straight. Oh and two things to note: -Yes, I have to use vectors. I've no idea why. -There are global …

Member Avatar
Member Avatar
+0 forum 4

void quick_sort (int *a, int n) { if (n < 2) return; int p = a[n / 2]; int *l = a; int *r = a + n - 1; while (l <= r) { while (*l < p) l++; while (*r > p) r--; if (l <= r) { int t = *l; *l++ = *r; *r-- = t; } } quick_sort(a, r - a + 1); quick_sort(l, a + n - l); } int main () { int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; int n = sizeof a / sizeof a[0]; …

Member Avatar
Member Avatar
+0 forum 3

Quickselect, based on quicksort, and counting select, based on counting sort. Each is capable of finding the kth smallest element in an unsorted/sorted list/array. This is some example code for a QuickSelect algorithm. This doesn't include the partition function. // return the kth smallest item int quickSelect(int items[], int first, int last, int k) { int pivot = partition(items, first, last); if (k < pivot-first) { return quickSelect(items, first, pivot, k); } else if (k > pivot) { return quickSelect(items, pivot+1, last, k-pivot); } else { return items[k]; } } Counting select, based on the counting sort algorithm, looks something …

Member Avatar
Member Avatar
+0 forum 1

Having trouble getting the QuickSort to work in this code. I turned off the counter for now, just trying to get the sorted array to display correctly. This is the results I get from the code: This program keeps track of the number of comparisons required to to sort a randomly generated array array. How large do you want the array to be? 4 Array to be sorted is: 677 419 981 377 The sorted array is: -858993460 -858993460 -858993460 -858993460 Press any key to continue . . . Here is the code I'm using [code] #include <iostream> #include <iomanip> …

Member Avatar
Member Avatar
+0 forum 4

I have a problem with this code : [CODE] #include<iostream> using namespace std; void qsort(int A[], int len) { if(len>=2){ int l=0; int u=len-1; int pivot=A[rand()%len]; while(l<u) { while(A[l]<pivot)l++; while(A[u]>pivot)u--; swap(A[l], A[u]); } qsort(A,l); qsort(&A[l+1],len-l-1); } else{return;} } void swap(int a, int b) { int temp; temp=a; a=b; b=temp; } void printlist(int l[],int len) { int i; for(i=0;i<len;i++) { cout<<l[i]<<endl; } } int main(int argc, char *argv[]) { int list[12]={333,250,323,12,9,900,0,732,56,88,72,12}; printlist(list,12); cout<<endl; qsort(list,12); printlist(list,12); return 0; } [/CODE] It’s working well if the element of array <=11, if more than 11 the program will crash, can anybody find the problem.. …

Member Avatar
Member Avatar
+0 forum 1

Hi.... I wrote a program for Quick Sort algorithm.... It is compiled fine....but it is giving a run time error i.e., Segmentation Fault.... I tried hard but couldn't find out what is that thing causing segmentation error in this program.... Please help.... I'm getting segmentation fault very frequently (i'm using gcc compiler).....why? Any help would be highly appreciated... Code[CODE]#include<stdio.h> int quick(int a[],int left,int right){ if(left<right){ int newpivi; newpivi=partition(a,left,right); //positioning pivot in its correct position....... quick(a,left,newpivi-1); //left part of the pivot element.... quick(a,newpivi+1,right); //right part of the pivot element..... } } int partition(int a[],int left,int right){ //partition function for positioning pivot …

Member Avatar
Member Avatar
+0 forum 10

Hi, I'm getting segmentation fault errors when I use quicksort with ~350 000+ numbers. This is the quick sort algorithm I'm using: [CODE]void swap(int* v, int i, int j) { int tmp = v[i]; v[i] = v[j]; v[j] = tmp; } int partition(int *v, int s, int e) { int p = v[e], i = s - 1; for (int j = s; j < e; j++) { if (v[j] <= p) { i++; swap(v, i, j); } } i++; swap(v, i, e); return i; } void quicksort(int* v, int s, int e) { if (s < e) { int …

Member Avatar
Member Avatar
+0 forum 6

I've this quicksort code, and it compiles. The thing is, I don't know how to give random values (integers) to the vector. The program should ask for the vector's size and then create the x random integers so it can apply the quiksort method. [CODE]#include "stdafx.h" #include <iostream> #include <vector> #include <stdlib.h> using namespace std; template <class T> void quick_sort (vector<T> &v, int low, int high){ //DO NOT SOLVE WHEN FACED WITH ONLY 1 OR 2 ELEMENTS if (low == high) {return;} else if (low + 1 == high){ if (v[low] < v[high]){ swap(v[low], v[high]); } return; } //PIVOTE int …

Member Avatar
Member Avatar
+0 forum 3

I keep getting a stackOverflow error in my quickSort and I can not figure out why. Any help would be greatly appreciated!! [CODE] private static void quickSortRecPriv(int[] arr, int first, int last, int ps) { int pivot = arr[first]; int left = first; int right = last; if (arr == null || first < 0 || last >= arr.length - 1) { throw new IllegalArgumentException(); } if (arr.length < 1) { return; } if(arr.length < ps) { InsertionSorter.insertionSort(arr); return; } while ( true ) { while ( arr[left] < pivot ) left++; while ( arr[right] > pivot ) right--; if …

Member Avatar
Member Avatar
+0 forum 1

CONVERT THIS QUICK SORT PROGRAM INTO PARTITION OF 3,5,7OR 11 ELEMENTS. [CODE] #include"stdafx.h" #include<iostream> using namespace std; #include <stdio.h> #include <stdlib.h> #define size 50 void swap(int *x,int *y) { int temp; temp = *x; *x = *y; *y = temp; } int partition(int i,int j ) { return((i+j) /2); } void quicksort(int list[],int m,int n) { int key,i,j,k; if( m < n) { k = partition(m,n); swap(&list[m],&list[k]); key = list[m]; i = m+1; j = n; while(i <= j) { while((i <= n) && (list[i] <= key)) i++; while((j >= m) && (list[j] > key)) j--; if( i < j) …

Member Avatar
Member Avatar
+0 forum 2

pls any one tell me why the loop is not ending?? (program for quick sort)[CODE][/CODE] [CODE]#include<stdio.h> int partition(int a[],int l,int r); void quicksort(int a[],int low,int high); int loc,temp,pivot,a[50],low,high,left,right; int main() { int n,i; printf("\nEnter the no: of elements : " ); scanf("%d",&n); printf("\nEnter the numbers : "); for(i=0;i<n;i++) { printf(" %d ",i); scanf("%d",&a[i]); } // printf("\n%d %d ok",i,i+900); low=0; high=n-1; quicksort(a,low,high); for(i=0;i<n;i++) printf(" %d",a[i]); return 0; } void quicksort(int a[],int low,int high) { left=low; right=high; while(left<right) { loc=partition(a,left,right); quicksort(a,left,(loc-1)); quicksort(a,(loc+1),right); } } int partition(int a[50],int l,int r) { pivot=a[l]; low=l-1; high=r+1; while(low<=high) { while(pivot<=a[high]&&low<high) high=high-1; while(pivot>=a[low]&&low<high) low=low+1; temp=a[high]; a[high]=a[low]; a[low]=temp; …

Member Avatar
Member Avatar
+0 forum 3

Hi I am trying to put quicksort in my class like other methods and call it using the main method, I did it for Selection, Insertion, Bubble Sort and I need one more which is quicksort. I already made the calling code for quicksort but I don't know how to use quicksort in class. I have the main method first then I have the classes Main [CODE]/**ICS * @(#)sorting_problem_setting.java * * sorting_problem_setting application * author * James Samuel * 29/March/2011 */ public class sorting_problem_setting { public static void main(String[] args) { SortClass sl = new SortClass(); // bubble sort int …

Member Avatar
Member Avatar
+0 forum 2

Hello, Can anybody explain to me how can I do: Implement the Random partitioning version of Quicksort. Take care that your data array is not copied (by value) into your subroutines, because you will sort the RandomEnglishDictionary.txt file. Report the first, 1000th and last elements in your sorted list. Thanks

Member Avatar
Member Avatar
+0 forum 5

I was humming along, and decided to try out data sorting. So, I did a few pieces of research, and came up with a really cool looking algorithm: Quicksort. I did what I should have, and started to program. Now, here is where I sound like an idiot: Why is this not working? The code is attached below. I wrote it up in Microsoft Visual Basic C++ 2010 Express. Every time I run it it gets the following error, and I cannot for the life of me find out why. Any help (at all) would be greatly appreciated, as I …

Member Avatar
Member Avatar
+0 forum 3

This quicksort implements the basic recursive algorithm with three improvements. The first improvement is choosing the pivot based on the median of three values in the list to be sorted. This minimizes the chances of a worst case scenario. The second improvement speeds up the algorithm by termination when subfiles of a certain size are reached. At that point continuing the recursion is not as effective as calling insertion sort on the almost sorted list. The last improvement protects against worst case behavior if there are large numbers of duplicates on the list by partitioning three ways instead of two: …

Member Avatar
Member Avatar
+1 forum 7

The End.