Battlefront3.net

[Matthew]

Quicksort is fast and easy. Pseudocode:

Code: Select all

Function Quicksort(list):
    if(list.len == 1):
        return list
    pivot = list.len/2 - 1;
    if(list[pivot] > list[pivot + 1]):
        return Quicksort(Sublist(list,0,pivot)) + Quicksort(Sublist(list,pivot + 1,list.len-1))
    else:
        return Quicksort(Sublist(list,pivot + 1,list.len - 1)) + Quicksort(Sublist(list,0,pivot))

Something like that. The list is split into two and the two parts are arranged based upon the middle 'pivot' values. THe two sides are processed recursively.

[Scott]

I haven't looked into the different sorting methods (quick, bubble, ect) but I have created one before. I gotta study up

Here is what I am doing:

Code: Select all

vector <char> mySort(vector <char> Letters)
{
    vector <char> Sorted;
    Sorted.reserve(Letters.size());

    int vectorLocation = 0;

    for (int i = 0; i < Letters.size(); i++)
    {
        if (Letters[i] < Sorted[vectorLocation])
        {
            Sorted[vectorLocation+1] = Sorted[vectorLocation];
            Sorted[vectorLocation] = Letters[i];
        }
    }

    return Sorted;
}

The thing is, I don't really know how to return Sorted. Would I use a pointer? If so, how do I point to a vector?

[Matthew]

I don't know how to return vectors.

To return an array I'd use a pointer.

[Scott]

I don't know how to return vectors.

*faint*

To return an array I'd use a pointer.

I want a dynamic amount of data to be collected so I'm stuck with a vector.

EDIT:

I have looked at quick sort. It's pretty neat! Damn programming is cool Anyway, as you know, I have a difficulty with recursion but before that here is what I have:

Code: Select all

#include <iostream>
#include <vector>

using namespace std;

vector <char> mySort(vector <char> Letters);

int main()
{
    vector <char> Chars;
    vector <char> CharsSorted;
    char chars = 97;

    for (int i = 0; i < 10; i++)
    {
        Chars.push_back(chars);
        chars++;
    }

    Chars = mySort(Chars);

    for (int i = 0; i < Chars.size(); i++)
    cout << Chars[i] << ", ";

    return 0;
}

vector <char> mySort(vector <char> Letters)
{
    vector <char> Less;
    vector <char> Greater;

    Less.reserve(Letters.size());
    Greater.reserve(Letters.size());

    for (int i = 1; i < Letters.size()-1; i++)//A
    {
        if (Letters[Letters.size()] > Letters.size()-i)
        Less.insert(Less.begin(), Letters[Letters.size()-1]);
        Letters.erase(Letters.end()-1);
    }
    for (int i = 0; i < Letters.size(); i++)//B
    {
        Greater.push_back(Letters[i]);
    }
    for (int i = 1; i > Letters.size()-1; i++)//A
    {
        if (Letters[Letters.size()] > Letters.size()-i)
        Greater.insert(Greater.begin(), Letters[Letters.size()-1]);
        Letters.erase(Letters.end()-1);
    }
    for (int i = Greater.size()-1; i > -1; i--)//B
    Less.insert(Less.begin(), Greater[i]);

    return Less;
}

The A and B comments are for parts that I think I can make reoccur. I am really tired right now so my mind isn't thinking properly but I just wanted to share what I did.

On a related note: what is the fastest sorting method? How do you understand the worst, best, average case symbols and equations? Thanks

[Matthew]

Quicksort is generally considered the best overal algorithm by many people.

The algorithm I wrote there isn't a quicksort. I think I was getting confused with the merge-sort which is usually slightly slower but more consistent. It's been a while. This is the quicksort:

Code: Select all

Function Quicksort(list):
    if list.len == 1:
        return list
    pivot = list.random_element //Prevents worst case scenario
    right = new_list()
    left = new_list()
    for val in list:
        if val > pivot:
            right.append(val)
        else:
            left.append(val)
    return Quicksort(left) + Quicksort(right)
            

That is the quicksort algorithm. I even checked. You place values into two sides of a pivot depending on if they are greater or lesser and recursively do the rest.

You do not need to use a vector to get a dynamic amount of data. Use the new statement in C++ or preferably malloc in either C or C++.

I'm going to make a quicksort algorithm in C...

[Scott]

I read up on quicksort and I'm pretty sure I created a quicksort (or at least a quicksort-esque) algorithm.

I prefer vectors than new. There are more methods available and just generally safer to use.

Do you know how to understand the best, worst, and average cases?

[Matthew]

Big-O notation? Yes, that makes perfect sense to me. Ignore the O. What is in the brakets explains everything. The n is the number of items to process.

Eg.

O(nlogn)

That means the complexity of an algorithm relative to n is n times a logarithm of n. The complexities are ordered like:

O(1)
O(n)
O(logn)
O(nlogn)
O(n^2)
O(2^n)
O(n!)

[Matthew]

I've completed a quicksort for strings in C:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdarg.h>
#include <string.h>

typedef struct {
	char ** string_array;
	int length;
} StringListStruct;

typedef StringListStruct * StringList;

StringList new_string_list(int len, ...){
	va_list args;
	StringList list = malloc(sizeof(StringListStruct));
	list->length = len;
	if (len) {
		va_start(args,len);
		list->string_array = malloc(sizeof(char *) * len);
		char * str;
		for (int x = 0; x < len; x++) {
			str = va_arg(args,char *);
			list->string_array[x] = malloc(sizeof(char) * strlen(str));
			strcpy(list->string_array[x],str);
		}
		va_end(args);
	}else{
		list->string_array = NULL;
	}
	return list;
}

StringList append_string(StringList list,char * string){
	list->length++;
	list->string_array = realloc(list->string_array, sizeof(char *) * list->length);
	list->string_array[list->length - 1] = malloc(sizeof(char) * strlen(string));
	strcpy(list->string_array[list->length - 1],string);
	return list;
}

StringList concatenate(StringList list1,StringList list2){
	StringList new_list = malloc(sizeof(StringListStruct));
	new_list->length = (list1->length + list2->length);
	new_list->string_array = malloc(sizeof(char *) * new_list->length);
	int y = 0;
	for (int x = 0; x < list1->length; x++) {
		new_list->string_array[y] = list1->string_array[x];
		y++;
	}
	for (int x = 0; x < list2->length; x++) {
		new_list->string_array[y] = list2->string_array[x];
		y++;
	}
	free(list1->string_array);
	free(list2->string_array);
	free(list1);
	free(list2);
	return new_list;
}

void free_list(StringList list){
	for (int x = 0; x < list->length; x++) {
		free(list->string_array[x]);
	}
	free(list->string_array);
	free(list);
}

StringList string_quicksort(StringList list){
	if (list->length < 2) {
		return list;
	}
	StringList left = new_string_list(0);
	StringList right = new_string_list(0);
	int pivot = random() % list->length;
	for (int x = 0; x < list->length; x++) {
		if (pivot == x) {
			continue;
		}
		if (strcmp(list->string_array[x],list->string_array[pivot]) > 0) {
			append_string(right, list->string_array[x]);
		}else{
			append_string(left, list->string_array[x]);
		}
	}
	char * pivot_str = malloc(sizeof(char) * strlen(list->string_array[pivot]));
	strcpy(pivot_str,list->string_array[pivot]);
	free_list(list);
	left = string_quicksort(left);
	append_string(left,pivot_str);
	free(pivot_str);
	return concatenate(left, string_quicksort(right));
}

void print_string_list(StringList list){
	putchar('[');
	for (int x = 0; x < list->length; x++) {
		if (x) {
			fputs(", ", stdout);
		}
		fputs(list->string_array[x],stdout);
	}
	puts("]");
}

int main (int argc, const char * argv[]) {
	srand(time(NULL));
	StringList list = new_string_list(12,"Peter","Stuart","Amy","James","Mark","Lewis","Harry","James","Simon","Jake","Jack","Peter");
	print_string_list(list);
	list = string_quicksort(list);
	print_string_list(list);
	free_list(list);
	return 0;
}

[Scott]

I get 7 errors when I try to compile that. And yes, I am using a C compiler.

[Matthew]

Helps if I know what they are... because I don't have them.

It took me a while to do that actually. I had a problem that took me forever to find. I kept overlooking a function call which freed the data before I wanted to use it for some purpose.

[Scott]

Helps if I know what they are... because I don't have them.

C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c: In function 'new_string_list':
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:25: error: 'for' loop initial declarations are only allowed in C99 mode
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:25: note: use option -std=c99 or -std=gnu99 to compile your code
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c: In function 'concatenate':
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:55: error: 'for' loop initial declarations are only allowed in C99 mode
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:60: error: redefinition of 'x'
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:55: note: previous definition of 'x' was here
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:60: error: 'for' loop initial declarations are only allowed in C99 mode
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c: In function 'free_list':
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:74: error: 'for' loop initial declarations are only allowed in C99 mode
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c: In function 'string_quicksort':
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:91: error: 'for' loop initial declarations are only allowed in C99 mode
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c: In function 'print_string_list':
C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.c:118: error: 'for' loop initial declarations are only allowed in C99 mode

[Matthew]

The problem is quite clear. You are using an out-dated C version. You need the C99 specification. Use the compiler option -std=c99 and that should compile the code perfectly.

[Scott]

Okay, but I still get one error:

C:\Documents and Settings\Derek\My Documents\Programming Folders\C Programs\anothertest.o:anothertest.c:(.text+0x2be): undefined reference to `random'

[Matthew]

Whoops, change random() to rand().

[Scott]

There we go. Nice. I am getting help from the C++ forum about returning and recurring vectors.

EDIT:

Well, software engineers suck, I didn't get much out of them. If you are able to help me I'd be very appreciative

Code: Select all

#include <iostream>
#include <vector>
#include <time.h>
#include <stdlib.h>
#include <windows.h>

using namespace std;

vector <char> quickSort(vector <char> Letters);

int main()
{
    vector <char> Chars;
    vector <char> CharsSorted;
    char chars = 122;

    srand( (unsigned)time(0));

    for (int i = 0; i < 10; i++)
    {
        Chars.push_back(chars);
        chars -= (rand() % 10);
    }
    cout << "Before sort\n";
    for (int i = 0; i < Chars.size(); i++)
    cout << Chars[i] << ", ";

    Chars = quickSort(Chars);

    cout << "\nAfter sort\n";
    for (int i = 0; i < Chars.size(); i++)
    cout << Chars[i] << ", ";

    return 0;
}

vector <char> quickSort(vector <char> Letters)
{
    if (Letters.size() == 1)
    return Letters;

    int pivot = (rand() % Letters.size());

    vector <char> Less;
    vector <char> Greater;

    Less.reserve(Letters.size());
    Greater.reserve(Letters.size());

    for (int i = 0; i < Letters.size(); i++)
    {
        if (Letters[i] > Letters[pivot])
        {
            Greater.push_back(Letters[i]);
        }
        else
        {
            Less.push_back(Letters[i]);
        }
    }

    //PSEUDO
    return Less + Greater;
}