Quicksort - problem with null values [message #148864] |
Mon, 28 November 2005 15:06 |
remiz
Messages: 5 Registered: November 2005
|
Junior Member |
|
|
I need to implement quicksort algorithm in PL/SQL. I have done this in this way (I don’t care about efficiency much):
TYPE int_arr IS TABLE OF INTEGER INDEX BY BINARY_INTEGER;
procedure qsort(arr in out int_arr, lo in INTEGER, hi in INTEGER ) is
i INTEGER := lo;
j INTEGER := hi;
x INTEGER := arr((lo+hi)/2);
tmp INTEGER;
begin
LOOP
WHILE (arr(i) < x) LOOP
i := i + 1;
END LOOP;
WHILE arr(j) > x LOOP
j := j - 1;
END LOOP;
IF i <= j THEN
tmp := arr(i);
arr(i) := arr(j);
arr(j) := tmp;
i := i + 1;
j := j - 1;
END IF;
EXIT WHEN i > j;
END LOOP;
IF lo < j THEN
qsort(arr, lo, j);
END IF;
IF i < hi THEN
qsort(arr, i, hi);
END IF;
end qsort;
This works for integers, but fails to sort null values. However I need to sort null values too. I tried to do it in this way:
WHILE (arr(i) < x) OR (arr(i) IS NULL) LOOP
i := i + 1;
END LOOP;
But this cause infinitive loop. Can anyone explain why this happens and how to sort those null values?
|
|
|
|
Re: Quicksort - problem with null values [message #148928 is a reply to message #148864] |
Tue, 29 November 2005 02:15 |
remiz
Messages: 5 Registered: November 2005
|
Junior Member |
|
|
My dear friend, by saying "I don't care about performance", I mean, that this implementation of quicksort is completely recursive, selection of the pivot is random and so on… What I need is working implementation of quicksort which sorts integers and nulls.
|
|
|
Re: Quicksort - problem with null values [message #148937 is a reply to message #148928] |
Tue, 29 November 2005 02:47 |
|
Maaher
Messages: 7065 Registered: December 2001
|
Senior Member |
|
|
I know, I know...I was just pulling your leg
I've created a small example how one could easily sort. I used a SQL type because it is usable in a SQL statement.
Here's the test code:
PROMPT SQL TYPE creation
CREATE TYPE int_arr IS TABLE OF INTEGER;
/
REM PROMPT FUNCTION CREATION
CREATE PROCEDURE qsort(p_arr IN OUT int_arr)
IS
new_arr int_arr := new int_arr();
BEGIN
FOR rec IN ( SELECT column_value FROM TABLE(p_arr) ORDER BY column_value NULLS FIRST)
LOOP
new_arr.extend();
new_arr(new_arr.last) := rec.column_value;
END LOOP;
p_arr := new_arr;
END qsort;
/
sho err
PROMPT Fill the type
SET SERVEROUT ON
DECLARE
v_arr int_arr := new int_arr( 18, 19, 16, 3, 19, 5, 2, 2, NULL, 3, NULL
, 17, 4, 6, 15, 7, 10, 14, 6, 15, NULL);
BEGIN
qsort(v_arr);
FOR j IN v_arr.FIRST..v_arr.LAST
LOOP
dbms_output.put_line(j||':'||v_arr(j));
END LOOP;
END;
/
PROMPT cleanup
DROP PROCEDURE qsort
/
DROP TYPE int_arr
/
When I ran it (as C:\useful\orafaq.sql) it gave this:
SQL> @C:\useful\orafaq
SQL TYPE creation
Type created.
Procedure created.
No errors.
Fill the type
1:
2:
3:
4:2
5:2
6:3
7:3
8:4
9:5
10:6
11:6
12:7
13:10
14:14
15:15
16:15
17:16
18:17
19:18
20:19
21:19
PL/SQL procedure successfully completed.
cleanup
Procedure dropped.
Type dropped.
SQL> Note how easy the procedure is.
MHE
|
|
|
|
|
Re: Quicksort - problem with null values [message #148990 is a reply to message #148864] |
Tue, 29 November 2005 07:37 |
remiz
Messages: 5 Registered: November 2005
|
Junior Member |
|
|
I have solved this problem. I implemented a little bit different quicksort algorithm and compare function which treats nulls as the smallest values. Now it works. I appreciate your help. Now I have to present this piece of crap to my professor...
|
|
|
Re: Quicksort - problem with null values [message #148996 is a reply to message #148990] |
Tue, 29 November 2005 08:07 |
|
Maaher
Messages: 7065 Registered: December 2001
|
Senior Member |
|
|
Glad you found it out!
you were the faster typer because in the mean time I've seen what you were missing:
NVL
The principle is the same: replace NULL by -1 (by using NVL where applicable).
But you've found the same principle yourself.
It's not such a strange assignment though. In my Oracle class it was "bubble sort" and "fibonacci" if I remember right .
MHE
[Updated on: Wed, 30 November 2005 00:57] Report message to a moderator
|
|
|
|
|