aboutsummaryrefslogtreecommitdiff
path: root/src/sort.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/sort.c')
-rw-r--r--src/sort.c426
1 files changed, 426 insertions, 0 deletions
diff --git a/src/sort.c b/src/sort.c
new file mode 100644
index 0000000..ee9a40b
--- /dev/null
+++ b/src/sort.c
@@ -0,0 +1,426 @@
+#include "table.h"
+#include <stdlib.h>
+
+int i_hoarepartition(double* arr, int low, int high){
+ double pivot = arr[((int)((high - low) / 2)) + low];
+ int i = low - 1;
+ int j = high + 1;
+
+ for(;;){
+ i++; j--;
+
+ while(arr[i] > pivot) i++;
+ while(arr[j] < pivot) j--;
+ if(i >= j) return j;
+
+ i_swap(arr[i],arr[j]);
+ }
+}
+
+void i_quicksort(double* arr, int low, int high){
+ if(low >= 0 && high >= 0 && low < high){
+ int p = i_hoarepartition(arr, low, high);
+ i_quicksort(arr, low, p);
+ i_quicksort(arr, p + 1, high);
+ }
+}
+
+int l_quicksort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+
+ i_quicksort(nums, 0, len - 1);
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
+
+void i_merge(double* arr, int b, int m, int e){
+ int n1 = m - b + 1;
+ int n2 = e - m;
+
+ double* left = malloc(sizeof * left * n1);
+ double* right = malloc(sizeof * right * n2);
+
+ for(int i = 0; i < n1; i++) left[i] = arr[b + i];
+ for(int i = 0; i < n2; i++) right[i] = arr[m + 1 + i];
+
+ int l_ind = 0;
+ int r_ind = 0;
+ int k = b;
+
+ for(; l_ind < n1 && r_ind < n2; k++){
+ if(left[l_ind] >= right[r_ind]){
+ arr[k] = left[l_ind];
+ l_ind++;
+ } else {
+ arr[k] = right[r_ind];
+ r_ind++;
+ }
+ }
+
+ for(; l_ind < n1; k++){
+ arr[k] = left[l_ind];
+ l_ind++;
+ }
+ for(; r_ind < n2; k++){
+ arr[k] = right[r_ind];
+ r_ind++;
+ }
+
+ free(left);
+ free(right);
+}
+
+void i_mergesort(double* arr, int b, int e){
+ if(b < e){
+ int mid = (b + e) /2;
+ i_mergesort(arr, b, mid);
+ i_mergesort(arr, mid + 1, e);
+ i_merge(arr, b, mid, e);
+ }
+}
+
+int l_mergesort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+
+ i_mergesort(nums, 0, len - 1);
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
+
+void i_heapify(double* arr, int n, int i){
+ int largest = i;
+ int left = 2 * i + 1;
+ int right = 2 * i + 2;
+
+ if(left < n && arr[left] < arr[largest])
+ largest = left;
+
+ if(right < n && arr[right] < arr[largest])
+ largest = right;
+
+ if(largest != i){
+ i_swap(arr[i],arr[largest]);
+ i_heapify(arr,n,largest);
+ }
+}
+
+int l_heapsort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+ for(int i = len / 2 - 1; i >= 0; i--)
+ i_heapify(nums,len,i);
+
+ for(int i = len - 1; i >= 0; i--){
+ i_swap(nums[i],nums[0]);
+ i_heapify(nums, i, 0);
+ }
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+ free(nums);
+ return 1;
+}
+
+int l_shellsort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+
+ for(int interval = len/2; interval > 0; interval /=2){
+ for(int i = interval; i < len; i++){
+ double temp = nums[i];
+ int j;
+ for(j = i; j >= interval && nums[j - interval] < temp; j -= interval){
+ nums[j] = nums[j - interval];
+ }
+ nums[j] = temp;
+ }
+ }
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
+
+int l_bubblesort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+
+ int n = len;
+ for(;n > 0;){
+ int new = 0;
+
+ for(int i = 0; i != n-1; i++){
+ if(nums[i+1]>nums[i]){
+ double temp = nums[i];
+ nums[i] = nums[i+1];
+ nums[i+1] = temp;
+
+ new = i+1;
+ }
+ }
+
+ n = new;
+ }
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
+
+int l_countingsort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ int* nums = malloc(sizeof * nums * len);
+ int* out = malloc(sizeof * nums * len);
+ int max = 0;
+ for(int i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ out[i] = 0;
+
+ if(nums[i]<0) p_fatal("array.countingsort(<table>) requires all indices to be >= 0");
+ max = max < nums[i] ? nums[i] : max;
+
+ lua_pop(L,1);
+ }
+
+ int* count = calloc(max + 1, sizeof * count);
+
+ for(size_t i = 0; i < len; i++){
+ count[nums[i]]++;
+ }
+
+ for(size_t i = 1; i <= max; i++){
+ count[i] += count[i - 1];
+ }
+
+ for(int i = len - 1; i >= 0; i--){
+ out[count[nums[i]] - 1] = nums[i];
+ count[nums[i]]--;
+ }
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,out[i]);
+ lua_settable(L, -3);
+ }
+
+ free(count);
+ free(nums);
+ free(out);
+ return 1;
+}
+
+int i_sorted(double* arr, size_t len){
+ for(size_t i = 0; i != len - 1; i++)
+ if(arr[i] > arr[i+1]) return 0;
+ return 1;
+}
+
+int l_miraclesort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+
+ for(;!i_sorted(nums,len););
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
+
+int l_stalinsort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ size_t rlen = 0;
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ double n = luaL_checknumber(L, -1);
+ if(rlen == 0 || nums[rlen - 1] <= n){
+ nums[rlen] = n;
+ rlen++;
+ }
+
+ lua_pop(L,1);
+ }
+
+
+ lua_newtable(L);
+ for(size_t i = 0; i != rlen; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
+
+void i_slowsort(double* arr, int i, int j){
+ if(i >= j) return;
+
+ int m = (i + j) /2;
+
+ i_slowsort(arr, i, m);
+ i_slowsort(arr, m + 1, j);
+
+ if(arr[j] < arr[m]){
+ i_swap(arr[j], arr[m]);
+ }
+
+ i_slowsort(arr, i, j - 1);
+}
+
+int l_slowsort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(int i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+
+ i_slowsort(nums, 0, len - 1);
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
+
+int l_bogosort(lua_State* L) {
+ luaL_checktype(L, 1, LUA_TTABLE);
+ size_t len = lua_objlen(L,1);
+ double* nums = malloc(sizeof * nums * len);
+ for(size_t i = 0; i <= len-1; i++){
+
+ lua_pushinteger(L,i+1);
+ lua_gettable(L,1);
+
+ nums[i] = luaL_checknumber(L, -1);
+ lua_pop(L,1);
+ }
+
+ for(;!i_sorted(nums, len);){
+ i_shuffle(nums, len);
+ }
+
+ lua_newtable(L);
+ for(size_t i = 0; i != len; i++){
+ lua_pushnumber(L,i+1);
+ lua_pushnumber(L,nums[i]);
+ lua_settable(L, -3);
+ }
+
+ free(nums);
+ return 1;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-13 08:31:30 +0000