C - Sorting Array of Pointers

[Team Cape]

This code is designed to work, not necessarily to be efficient. If it does not work, point me in the right direction, please, or tell me how (and why!) a certain fix would work.

 

This code is meant to delete duplicates in an array of strings and order them by collating sequence.

 

Example: 

If given the strings "africa", "asia", "africa", "europe"

you would get back:

"asia", "africa", "europe"

void sortUnique (char** pWords) {
    char* temp;
    int cmp;

    for(int i = 0; pWords[i]; i++) {
        for(int j = (i+1); pWords[j]; j++) {
            cmp = strcmp(pWords[i], pWords[j]);
            if(cmp > 0) {
                temp = pWords[j];
                pWords[j] = pWords[i];
                pWords[i] = temp;
            } else if(cmp == 0) {
                pWords[j] = NULL;
            }
        }
    }
}

[Solzhenitsyn]

capital theta(n^2)  although i know that you don't care about efficiency right now.

 

What do you think using address the numeric value of each address as a basis to perform a quicksort, and then you march through your array one time to search for duplicates? That would bring you down to capital theta(n log(n)), but maybe the k_1 constant will be high enough that you lose overall efficiency. 

[Team Cape]

capital theta(n^2)  although i know that you don't care about efficiency right now.

 

What do you think using address the numeric value of each address as a basis to perform a quicksort, and then you march through your array one time to search for duplicates? That would bring you down to capital theta(n log(n)), but maybe the k_1 constant will be high enough that you lose overall efficiency. 

 

we're designing a pretty short program, and because we rushed into C just a few days ago (we did assembler for a few weeks before), he doesnt expect us to be efficient, but he wants us to be able to think through prompts like this. i think it works, but i cant test it because i'm having strange issues with my compiler - aside from the (very bad) efficiency, does it look alright?

[Solzhenitsyn]

we're designing a pretty short program, and because we rushed into C just a few days ago (we did assembler for a few weeks before), he doesnt expect us to be efficient, but he wants us to be able to think through prompts like this. i think it works, but i cant test it because i'm having strange issues with my compiler - aside from the (very bad) efficiency, does it look alright?

 

It looks fine, you've implemented a bubble sort that also sets duplicate pointers to null. I haven't used C before (only C++14, and my exposure is limited at that) so don't take my advice with much seriousness but I'm surprised that your teacher is having you use strcmp to compare pointers. Is that normal?

 

If they are giving you string literals, I would have thought that the comparison should be performed by dereferencing pointers. This would save you an assignment operation and a fetch operation which as far as I know is much slower than handling as many operations as possible in your registers.

 

But again, I feel the need once again to declare my general ignorance on the matter and if there is someone with more education than me I would defer to their opinion. 

[Team Cape]

It looks fine, you've implemented a bubble sort that also sets duplicate pointers to null. I haven't used C before (only C++14, and my exposure is limited at that) so don't take my advice with much seriousness but I'm surprised that your teacher is having you use strcmp to compare pointers. Is that normal?

 

If they are giving you string literals, I would have thought that the comparison should be performed by dereferencing pointers. This would save you an assignment operation and a fetch operation which as far as I know is much slower than handling as many operations as possible in your registers.

 

But again, I feel the need once again to declare my general ignorance on the matter and if there is someone with more education than me I would defer to their opinion. 

 

you could be right - he said this assignment was about learning more about pointers. what were you thinking about how this might be done by dereferencing pointers?

Edited October 14, 2016 by Imateamcape

[Solzhenitsyn]

you could be right - he said this assignment was about learning more about pointers. what were you thinking about how this might be done by dereferencing pointers?

int main()
{
    int* a;
    a = malloc(sizeof(int));
    *a = 'a';
    int b = 16;

    if (&b == a) { // &b is a pointer to the address where the integer literal bound to b is stored
        // do something
    }
    
    return 0;
}

I think that this is how you do it -- I started with ASM/CPP, but I don't even have gcc installed any more so I can't actually check to see if this will compile. 

Edited October 14, 2016 by Solzhenitsyn

[Team Cape]

int main()
{
    int* a;
    a = malloc(sizeof(int));
    *a = 'a';
    int b = 16;

    if (&b == a) { // &b is a pointer to the address where the integer literal bound to b is stored
        // do something
    }
    
    return 0;
}

This way you aren't using a temporary storage variable.

 

I think that this is how you do it -- I started with ASM/CPP, but I don't even have gcc installed any more so I can't actually check to see if this will compile. x_X

 

 

changed it to this - probably uglier this way, but i think it's more in-line with what he wanted

    char* temp;
    int cmp;

    char** pOne = pWords;
    char** pTwo = pWords;

    while(*pOne) {
    	while(*pTwo) {
    		cmp = strcmp(*pOne, *pTwo);
    		if(cmp > 0) {
    			temp = *pTwo;
    			*pTwo = *pOne;
    			*pOne = temp;
    		} else if(cmp == 0) {
    			*pTwo = NULL;
    		}
    		pTwo++;
    	}
    	pOne++;
    }

[Solzhenitsyn]

 

changed it to this - probably uglier this way, but i think it's more in-line with what he wanted

 

<snip>

 

I think that they are the same, but personally I would go with the for-loop version (since the postfix operators seem to fit the convention of a for loop).

 

Side note; since you're the first person I've met who has done any assembly, check out this pseudo bubble sorting algorithm I implemented for fun.

.386                   ; Identifies minimum CPU required.
.MODEL flat, stdcall   ; Flat -> protected mode program, StdCall -> Can call Windows system functions.
.STACK 4096            ; Allocates 4096 bytes (1000h) for the stack.

; == Prototypes ==
ExitProcess PROTO,dwExitCode:DWORD                    ; From Win32, exits to Windows.
Clrscr PROTO                                          ; Irvine32, clears screen of contents.
ReadChar PROTO                                        ; Irvine32, pauses runtime until a key is run.
bubbleSort PROTO, arrayLoc:PTR DWORD, arraySize:DWORD ; Performs a bubble sort (O(n^2)) on a specified region of memory.

; == Data Segement == 

.data
    array       DWORD    1,3,3,4,5 ; Label to be sorted.

; == Code Segment ==
.code

; * Bubble Sort Procedure - Sorts a given memory region in descending order. Arguments: Pointer to array, size of array.
; A bubble sort marches through an array, comparing the current and next element. When the next element is greater than
; the current element, the two elements are swapped. The process is repeated as many times as is needed to successfully
; march through the array without finding an out of place element.
bubbleSort PROC USES eax ebx ecx esi,
    arrayLoc:PTR DWORD, arraySize:DWORD

    sub arrayLoc, type DWORD; Move the pointer back by four bytes.
    jmp setup               ; Begin instructions.

    swap:                   ; The instructions in this label will swap the values of the current and next elements.
        xchg eax, [esi+4]   ; Correct the value at next element
        mov [esi], eax      ; Correct the value at current element
        mov ebx, 1          ; A value has been modified, so raise flag.
        loop march          ; Continue marching if we are not at the end, otherwise fall through to setup next run.

    setup:                  ; The instructions in this label will set/reset program for it's next march.
        mov ebx, 0          ; Ebx will be used as a flag. When a swap is performed, ebx=1. When ebx=1, instead of exiting we march again.
        mov esi, arrayLoc   ; Set esi to the location in memory.
        mov ecx, arraySize  ; Set loop counter to the number of elements...
        dec ecx             ; ...less one.

    march:                  ; The instructions in this label will iterate through the memory region. If currElem<nextElem, then call swap label.
        add esi, type DWORD ; Look at the next element
        mov eax, [esi]      ; Store current element in eax
        cmp eax, [esi+4]    ; Compare current element and next element. 
        jl swap             ; If currElement<nextElement, then swap values.
        loop march          ; If we aren't done iterating through the array, then continue working. Otherwise, fall through.

    done:                   ; The instructions in this label will check to see if the memory region is sorted.
        cmp ebx, 0          ; If we made a swap operation, then ebx=1.
        jne setup           ; If a swap operation was made, then march again.
        ret                 ; Otherwise, return.

bubbleSort ENDP

main proc
    call Clrscr                                      ; Clear the screen
    invoke bubbleSort, OFFSET array, LENGTHOF array  ; Run the bubble sort
	call ReadChar		                     ; Pauses the runtime until a key is pressed.
    invoke ExitProcess, 0                            ; Exit runtime.
main ENDP
END main

Using Irvine32 lib for user I/O.

[porkcow]

why such useful tips on spam/off topic?

[Team Cape]

I think that they are the same, but personally I would go with the for-loop version (since the postfix operators seem to fit the convention of a for loop).

 

Side note; since you're the first person I've met who has done any assembly, check out this pseudo bubble sorting algorithm I implemented for fun.

.386                   ; Identifies minimum CPU required.
.MODEL flat, stdcall   ; Flat -> protected mode program, StdCall -> Can call Windows system functions.
.STACK 4096            ; Allocates 4096 bytes (1000h) for the stack.

; == Prototypes ==
ExitProcess PROTO,dwExitCode:DWORD                    ; From Win32, exits to Windows.
Clrscr PROTO                                          ; Irvine32, clears screen of contents.
ReadChar PROTO                                        ; Irvine32, pauses runtime until a key is run.
bubbleSort PROTO, arrayLoc:PTR DWORD, arraySize:DWORD ; Performs a bubble sort (O(n^2)) on a specified region of memory.

; == Data Segement == 

.data
    array       DWORD    1,3,3,4,5 ; Label to be sorted.

; == Code Segment ==
.code

; * Bubble Sort Procedure - Sorts a given memory region in descending order. Arguments: Pointer to array, size of array.
; A bubble sort marches through an array, comparing the current and next element. When the next element is greater than
; the current element, the two elements are swapped. The process is repeated as many times as is needed to successfully
; march through the array without finding an out of place element.
bubbleSort PROC USES eax ebx ecx esi,
    arrayLoc:PTR DWORD, arraySize:DWORD

    sub arrayLoc, type DWORD; Move the pointer back by four bytes.
    jmp setup               ; Begin instructions.

    swap:                   ; The instructions in this label will swap the values of the current and next elements.
        xchg eax, [esi+4]   ; Correct the value at next element
        mov [esi], eax      ; Correct the value at current element
        mov ebx, 1          ; A value has been modified, so raise flag.
        loop march          ; Continue marching if we are not at the end, otherwise fall through to setup next run.

    setup:                  ; The instructions in this label will set/reset program for it's next march.
        mov ebx, 0          ; Ebx will be used as a flag. When a swap is performed, ebx=1. When ebx=1, instead of exiting we march again.
        mov esi, arrayLoc   ; Set esi to the location in memory.
        mov ecx, arraySize  ; Set loop counter to the number of elements...
        dec ecx             ; ...less one.

    march:                  ; The instructions in this label will iterate through the memory region. If currElem<nextElem, then call swap label.
        add esi, type DWORD ; Look at the next element
        mov eax, [esi]      ; Store current element in eax
        cmp eax, [esi+4]    ; Compare current element and next element. 
        jl swap             ; If currElement<nextElement, then swap values.
        loop march          ; If we aren't done iterating through the array, then continue working. Otherwise, fall through.

    done:                   ; The instructions in this label will check to see if the memory region is sorted.
        cmp ebx, 0          ; If we made a swap operation, then ebx=1.
        jne setup           ; If a swap operation was made, then march again.
        ret                 ; Otherwise, return.

bubbleSort ENDP

main proc
    call Clrscr                                      ; Clear the screen
    invoke bubbleSort, OFFSET array, LENGTHOF array  ; Run the bubble sort
	call ReadChar		                     ; Pauses the runtime until a key is pressed.
    invoke ExitProcess, 0                            ; Exit runtime.
main ENDP
END main

Using Irvine32 lib for user I/O.

 

this goes some beyond the scope of what i've done (i'm in a post-ap high school course), but from what i understand this is very interesting good shit dude