SQL Server: purging bulk records doesn't decrease database file size

I started with a 49,017,920 KB database with a 984,064 KB index. (Used a backup copy for testing, I should say.)
We purged about 1/3 of the records in the entire database from main tables, etc. throughout.

1. Did a database Shrink, with the checkbox to reorganize files.
2. This made the file size 44,195,776. And the index was 1024 KB.
3. I right clicked the indexes on the most active, largest table by row count, and did a REBUILD ALL. This brought the sizes UP to 45,322,176KB and the index to 82,944 KB.

I thought removing 1/3 of the records would greatly decrease the size of the database.

Is there something else I need to do to release unused space or something? What am I seeing here?

Thanks!